网站如何收录快,聚兴大宗商品交易平台,wordpress分权限浏览器,网站空间支付方式数据结构#xff08;五#xff09;——图
1. 图的基本概念
1.1 图的定义 1.2 有向图和无向图 在有向图中#xff0c;使用圆括号表示一条边#xff0c;圆括号里元素位置互换没有影响。
在无向图中#xff0c;使用尖括号表示一条边#xff0c;尖括号里元素位置互换则表示…数据结构五——图
1. 图的基本概念
1.1 图的定义 1.2 有向图和无向图 在有向图中使用圆括号表示一条边圆括号里元素位置互换没有影响。
在无向图中使用尖括号表示一条边尖括号里元素位置互换则表示的是不同的两条边。
1.3 简单图和多重图 简单图可以解决绝大多数的问题所以在数据结构里只研究简单图。
1.4 顶点的度、入度、出度 1.5 顶点-顶点的关系描述 1.6 连通图和强连通图 注意连通图是基于无向图的强连通图是基于有向图的。
1.7 子图 所谓子图就是A图的结点和边是B图的子集则称A为B的子图。若A的结点数等于B的结点数则称A为B的生成子图。上面是无向图的子图与生成子图在有向图中的概念是一样的如下。 1.8 连通分量 注意连通分量是基于无向图的概念无向图中的极大连通子图称为连通分量。
极大连通子图子图必须连通且包含尽可能多的顶点和边。
1.9 强连通分量 注意强连通分量是基于有向图的概念有向图中的极大强连通子图称为强连通分量。
极大强连通子图子图必须强连通同时保留尽可能多的边。
1.10 生成树 连通图的生成树是指包含图中全部顶点的一个极小连通子图。
极小连通子图边尽可能的少但要保持连通。
注意连通图的生成树的表示不唯一。
1.11 生成森林 非连通图中连通分量的生成树构成了非连通图的生成森林。
1.12 边的权带权图 边的权就是在一个图中每条边都可以标上具有某种含义的数值该数值称为该边的权值。这个数值可以代表距离重量等。
1.13 稀疏图和稠密图 注意上图虽然给了一个区分稀疏图和稠密图的公式但实际上并没有明确的界限即使使用上述公式求出来是稀疏图也可以说是稠密图。但考试时可以以这个为界去区分。
1.14 树和有向树 注意树是连通图但有向树不一定是强连通图。
1.15 图的概念小结 2. 图的存储
2.1 邻接矩阵法 上图是邻接矩阵法的存储图以及使用C语言的描述。
可以看到所谓邻接矩阵法就是使用一个一维数组存储图中顶点的信息再用一个二维数组存储图中边的信息而存储顶点之间的邻接关系的二维数组称为邻接矩阵。
上图使用Vex数组存储顶点对于无向图根据对应顶点的下标可以查找到该顶点在二维数组里所对应的行或列。也就是说可以通过查询A和D的下标进而可以找到以A为行以D为列对应位置的数据如果是1则说明两者之间有边0则没边。如下图的对应关系 对于有向图来说由于边带了方向所以查找时要确定查找的是谁到谁的边比如如果是从A到B的边就要把A当行把B当列去查找。一般存储时也是把边从谁射出谁当行射入谁谁当列。
下面看一下对于无向图和有向图如何分别求其顶点的度、入度和出度。 对于无向图求i个结点的度就是看第i行或第i列有几个1。如果有n个结点则有n行和n列所以查找i结点所对应的行或列的时间复杂度就是O(|V|)。
对于有向图第i个结点的出度就是求第i行有几个1入度就是求第i列有几个1。求度只需要把入度和出度加起来即可。同无向图一样求有向图的出度和入度的时间复杂度都是O(|V|)而求度的核心还是要求出度和入度所以求度的时间复杂度也是O(|V|)。
上面所说全都是不带权图对于不带权图只需要用0和1表示两种连接状态即可。下面看一下带权图的表示。 对于带权图来说数组里存储的就不在是表示连接状态的0和1而是在有边处存储上边的权值如上图。如果带权图里有两点之间没有边则对应的邻接矩阵里用0或无穷来表示有的时候也会使用邻接矩阵对角线上用0表示没有边其余地方用无穷表示没边。
带权图的C语言描述如上图对于无穷的表示可以通过使用int变量所存储的上限值来表示无穷另外在Edge数组里要把对应两点间的连接关系改为边的权值。
下面对邻接矩阵进行性能分析 使用领接矩阵法存储图及其边的关系如果图有n个结点就要建立一个n×n的数组所以空间复杂度为O(|V|2)。因此如果图中边数很少使用此方法就会浪费大量的存储空间所以领接矩阵法适合存储稠密图。
另外不难发现无向图的领接矩阵是对称矩阵所以可以压缩存储空间即存储上三角或下三角。这部分内容在我写的数据结构二——栈与队列与数组中可以回去复习一下。
最后看一下邻接矩阵的性质 上图已经给出了领接矩阵的性质这里再稍微解释一下例如上图下的例子A2[1][4]1表示的就是从A结点到D结点长度为2的路径的数目为1。对于图G的领接矩阵AA2可以得到右下角的矩阵这个矩阵里对应两个结点确定的数值表示从一个结点到另一个结点长度为2的路径的数目。所以在考试时如果其一个图的某点到另一点的长度为n的路径的数目我们可以先写出其领接矩阵然后将n个领接矩阵相乘得到最后的矩阵再根据要找的两个点找到由该两点确定的矩阵位置上的数据这就是两点间的长度为n的路径的数目。
2.2 邻接表法
上面使用的领接矩阵法是用数组实现的顺序存储空间复杂度较高不适合存储稀疏图。所以这部分学习邻接表法存储图邻接表法是通过顺序链式存储实现的使用邻接表可以减少不必要的空间浪费。 上图是领接表的存储结构及C语言描述。
可以用一维数组来存储各个顶点的信息然后对于每个顶点可以通过指针指向它的第一条边边的描述如上图左下对于每一条边它还可以指向下一条与顶点相连边。当最后一个与顶点相连的边没有可指的地方时就会令它的指向下一条弧的指针为NULL表示之后再无与顶点相连的边。可以参考上图的例子来辅助理解。
下面看一下有向图的领接表 有向图的邻接表存储思路与无向图一致只不过需要注意弧的方向性。
到这里再细看无向图的邻接表法可以发现无向图的边没有方向性按理说每个弧存储一遍就可以了但是邻接表里却存储了两遍这就导致边结点数量变成了2|E|整体空间复杂度就变成了O(|V|2|E|)。
而有向图由于边的方向性所以不存在存储两遍的问题所以有向图的整体空间复杂度就是O(|V||E|)。
现在思考一下如何求顶点的度、入度和出度
对于无向图来说没有出度和入度的概念所以找一个顶点的度只需要看后面跟了多少个弧即可。
而对于有向图来说若要看某一个顶点出度只需要看后面跟了多少个弧即可但对于入度则要遍历除该顶点外的每一个顶点查看每一个顶点后有没有指向该顶点的弧把所有顶点指向该顶点的弧的数量加起来才能求得入度度只需要把入度和出度相加即可。所以可以看到对于有向图来说吗找一个结点的入度是很麻烦的这也是有向图一个很大的缺点。
若要找到与顶点相连的边/弧实质就是找顶点的度所以可以参考上面的无向图和有向图找度。 这里再补充一点如上图邻接表法表示的图并不唯一如上图对于该无向图至少可以画出上面两种邻接表的表示。但对于邻接矩阵只要确定了顶点编号图的邻接矩阵表示方式就唯一确定了。
下面总结一下邻接表与邻接矩阵 这里说一下虽然邻接表适合存储稀疏图但对于无向图来说邻接表还是浪费了相当一部分资源所以邻接表比较适合的应该是存储有向图中的稀疏图不过这点知道即可考试时也可以直接说邻接表适合存储稀疏图这样也是对的。
2.3 十字链表存储有向图
上面说过邻接矩阵最主要的问题是空间复杂度太高而邻接表最主要的问题是当存储有向图找有向图的入边不方便。为此提出了十字链表法通过这种方法可以解决这两个问题。 十字链表结构如上图定义了顶点结点和弧结点分别代指顶点和弧另外这两个顶点的相关结构及对应字段的含义上图也都给出。此外上图下是对左下角有向图的十字链表的表示。这里可以结合图自己理解一下。
使用十字链表法存储有向图想要找到顶点的入度只需要沿着橙色指针往后遍历即可若想要找到顶点的出度只需要沿着绿色指针往后遍历即可。
下面分析一下十字链表法的性能 使用十字链表法存储有向图所需空间复杂度为O(|V||E|)同邻接表法一样优秀并不需要像邻接矩阵一样需要O(|V|2)的数量级。
另外注意十字链表只用于存储有向图。
2.4 邻接多重表存储无向图 使用邻接矩存储无向图的问题是空间复杂度太高。而邻接表最主要的问题是重复存储这时候进行删除操作如果要删除边还好只需要从边的两个顶点里删除即可但要删除顶点就很麻烦删除该顶点以后还要遍历邻接表找到与该顶点相连的顶点删去相连顶点里存储的与被删顶点相连的信息时间复杂度太高。所以提出了使用邻接多重表的方法来存储无向图。 邻接多重表和十字链表的存储一样只不过由于邻接多重表用于存储无向图所以不需要区分两个结点的左右顺序邻接多重表的存储可以结合上图例子进行理解。
下面看一下如果删除边的操作 上面是删除A和B相连的边找到对应的边结点删去以后由于橙色存储A顶点的边绿色存储B顶点的边为了防止删除以后A、B顶点指针无指向所以在删除之前要先顺着该边结点的橙色指针找到下一条边对应的结点让A指向然后再顺着该边结点的绿色指针找到下一条边对应的结点让B指向。
下面下如果删除顶点的操作 上面是删除顶点E的操作删除顶点E以后其所有指向的边结点也都要删除。除此以外其余若有指向E的边结点的指针都要置为NULL。
再来看一下邻接多重表的空间复杂度由于每条边只对应一份数据所以邻接多重表的时间复杂度为O(|V||E|)比邻接表的空间复杂度还要优秀。此外邻接多重表的删除边、结点等操作也很方便。但需要注意邻接多重表只适用于存储无向图。
2.5 图的存储小结 注意由于十字链表和邻接多重表比较复杂考试时一般不会要求手写代码所以对于这两种方式知道其一些特性即可。
3. 图的基本操作
3.1 图的基本操作总览 由于十字链表和邻接多重表比较复杂所以考研中常考的还是邻接矩阵和邻接表所以接下来只探讨邻接矩阵和邻接表的基本操作。
3.2 判断图G是否存在边或弧 对于无向图如果用邻接矩阵存储想判断两个顶点间是否有边只需要找到这两个顶点对应的元素是否为1即可因此采用邻接矩阵实现判断顶点间是否有边的操作只需要O(1)的时间复杂度。
如果用邻接表存储想判断两个顶点间是否有边只需要判断一个顶点的边结点是否有另一个结点即可。最好的时间复杂度为O(1)最坏的时间复杂度为O(|V|)。
所以如果存储无向图想实判断两个顶点间是否有边使用邻接矩阵法更好一点。 对于有向图实现判断两个顶点间是否有边的操作也是一样的重点是要记住有向图的边是有方向的要注意区分边的方向找到对应的顶点。
3.3 求图G中和结点x邻接的边 对于无向图如果用邻接矩阵存储想求和结点x邻接的边只需要遍历x对应的行或列检查哪些地方是1即可因此采用邻接矩阵实现需要O(|V|)的时间复杂度。
如果用邻接表存储想求和结点x邻接的边只需要遍历x的边结点即可。最好的时间复杂度为O(1)即只有一个边结点最坏的时间复杂度为O(|V|)即有|V|个边结点。
所以如果存储无向图想实现求和结点x邻接的边的基本操作使用邻接表法更好一点。 如果存储有向图想求和结点x邻接的边如果使用邻接矩阵求出边只要遍历x对应的行求入边只需要遍历x对应的列。时间复杂度为O(|V|)。
但如果使用邻接表遍历出边和无向图一样只需要遍历x的边结点即可。但遍历入边就需要遍历邻接表的所有边结点时间复杂度为O(|E|)。
所以如果存储有向图想实现求和结点x邻接的边的基本操作使用邻接矩阵法更好一点但也不是绝对的。比如说存储的是一个稀疏图这是|E|的值就很小此时使用邻接表法实现该功能也可以得到不错的表现。
3.4 在图G中插入顶点x 由于刚插入该顶点所以该顶点与其他顶点是不相连的。如果采用邻接矩阵存储只需要在保存这些顶点的数组后面的空白位置写入新结点的数据即可在邻接矩阵中与新结点对应的行和列就可以表现当前新结点与其他顶点的关系。此时刚插入新结点看似要在邻接矩阵里插入一堆0但是实际上矩阵化0操作应该是在矩阵初始化时就已经做好了所以插入新结点的唯一开销就是写入新结点的相关信息因此可以在O(1)的时间复杂度内完成。
如果采用邻接表存储只需要在数组末尾插入新结点信息即可由于新结点刚插入还没有连任何边所以把新结点指针设为NULL即可同样使用O(1)复杂度。
有向图也类似这里就不在叙述有向图。
3.5 在图G中删除顶点x 对于无向图以上图中删除C为例如果采用邻接矩阵存储就需要删除C对应的行和列即把C对应的行和列的数据清空。清空以后容易想到的方法就是把删除的行和列周围的元素在拼接起来但这样做会导致大量数据元素移动开销很大。所以可以采用置0的方法即删除C结点后只需要把C对应的行和列的数据变为0即可。然后在顶点的结构体当中添加一个bool变量用来表示C顶点的位置为空顶点。如下图使用这种方法只需要修改一行和一列的元素所以在O(|V|)时间内就可以完成。 如果使用邻接表存储删除顶点C还需要遍历其他顶点的边看有没有和C相连的边。最好的情况是C后面本身就没有边结点时间复杂度为O(1)最坏的情况是遍历完全部边结点时间复杂度为O(|E|)。
下面看有向图 对于有向图他的删除操作与无向图一样自己参阅上图。
3.6 若图G中没有某条边/弧则添加该边/弧 这里很简单唯一要说明的是邻接表里添加该边/弧如果采用尾插法则要遍历到最后一个边结点所以采用前插法可以将时间复杂度缩短到O(1)。
有向图也类似不过多叙述。
3.7 若图G中有某条边/弧则删除该边/弧 这个也很简单看图就可以理解有向图和无向图类似也不过多叙述。
3.8 求图G中顶点x的第一个邻接点 对于无向图如果用邻接矩阵存储想求顶点x的第一个邻接点只需要遍历x对应的行找到第一个1即可最好的时间复杂度为O(1)即第一个就为1最坏的时间复杂度为O(|V|)即最后一个为1。
如果用邻接表存储想求顶点x的第一个邻接点只需要往后找第一个边结点即可时间复杂度为O(1)。 对于有向图如果用邻接矩阵存储想求顶点x的第一个邻接点根据找出边还是入边只需要遍历x对应的行或列找到第一个1即可最好的时间复杂度为O(1)即第一个就为1最坏的时间复杂度为O(|V|)即最后一个为1。
如果用邻接表存储想求顶点x的第一个邻接点如果找的是出边邻接点只需要往后找第一个边结点即可时间复杂度为O(1)。但如果找的是入边的邻接点最好的情况是遍历的第一个边结点就是入边邻接点时间复杂度为O(1)最坏的情况是最后一个才遍历到复杂度为O(|E|)。
3.9 求图G中x的第二个邻接点 对于无向图如果用邻接矩阵存储想求顶点x的第二个邻接点只需要从x对应的行的第一个邻接点向后遍历找到第二个数值为1的邻接点即可最好的时间复杂度为O(1)即第一个就为1最坏的时间复杂度为O(|V|)即最后一个为1。
如果用邻接表存储想求顶点x的第二个邻接点只需要从x对应的第一个边结点向后找一个即可时间复杂度为O(1)。
有向图的做法也类似但是需要注意的是如果是有向图要看找的是出边邻接点还是入边邻接点然后在3.8有向图找第一个邻接点的基础上向后再找一个即可这里就不详细说明了。
3.10 设置/获取权值 设置和获取权值的操作和判断图G中边/弧是否存在的操作一致力因为设置和获取权值的核心就在于找到边所以设置和获取权值的开销和找边的开销一样这里不再叙述。
4. 图的遍历
4.1 广度优先遍历
广度优先搜索遍历图的过程是以v为起始点由近至远依次访问和v有路径相通且路径长度为1,2,……的顶点。 在树的部分我们也学过树的广度优先搜索如上图将树与图做比较不论是树还是图在进行广度优先搜索时都要实现通过某一个结点找到与之相邻的其它结点因为只有实现这个操作才可以一层一层的往下找到所有结点。
另外由于树结构不存在回路所以搜索相邻结点时只需要向下一直搜索即可。而图结构存在回路所以搜索相邻结点时还需要判断当前搜所到的结点是否已经被搜索过了判断是否已经被搜索的方式很简单只需要给已经被搜索的点做上标记即可。
在实现树的广度优先遍历时需要一个辅助队列帮助所以对于图的广度优先遍历也可以设置一个类似的辅助队列。
下面是图的广度优先遍历的实现 要实现图的广度优先遍历关键在于三点一是找到与顶点相邻的所有顶点二是标记哪些顶点被访问过三是需要一个辅助队列来存储接下来要遍历的点。对于第一点可以使用在图的基本操作部分的FirstNeighbor和NextNeighbor函数。对于第二点可以定义一个bool型标记数组存储各个顶点的标记信息用false表示未被标记用true表示标记。对于第三点只需要定义一个辅助队列即可。
下面看一下代码实现 上图左边是以2为出发点实现广度优先搜索的例子右边是实现广度优先搜索的程序可以结合理解。
注意考试时可能会遇到给一个图G然后让以某个顶点为出发点然后写广度优先搜索序列的题目如上图左边的例子。
另外从上面的遍历序列的例子里不难发现我们在找6的邻接点时可以选3和7不过上面是按照递增的顺序来选的然而也可以先选7至于遍历序列究竟该如何选择这与图的存储方式有关如下图 如果图是以邻接矩阵的方式存储因为一个图的邻接矩阵表示方式唯一因此广度优先遍历序列唯一且是按照前面所说的递增顺序选取。
但是如果图是以邻接表的方式存储因为一个图的邻接表的表示方式不唯一因此广度优先遍历序列也不唯一如上图右。
接下来接着看广度优先的代码实现会发现当图是一个非连通图时就会无法遍历完所有结点如下图 这里对BFS进行了优化在广度优先遍历的代码之上添加了一个二次查看标记数组的标记号如果调用BFS以后标记数组仍存在标记位false的值就会以标记为false的结点为顶点再次使用广度优先搜索算法直到标记数组里没有未被访问的点为止。
这里总结出一个结论对于无向图调用BFS函数的次数连通分量数。
接下来对图的广度优先搜索算法进行复杂度分析 如果使用邻接矩阵存储所需要时间复杂度为O(|V|2)这个很简单就不多说。
如果使用邻接表存储所需要时间复杂度为O(|V||E|)这是因为访问|V|个顶点需要O(|V|)时间复杂度而邻接表存储无向图会存储两次前面有说过为什么存储两次查找各个顶点的邻接点需要2|E|的时间但大O表示法可以不计系数所以时间复杂度为O(|V||E|)。
这里会有疑问在分析上面BFS算法的时间复杂度时为什么没有像以前一样分析最深层循环的次数举个例子如果一个图没有边并且使用邻接表存储显然循环次数就为0次然而事实上对每一个结点的访问都要调用一次BFS因此访问所有结点也需要O(|V|)的时间所以只考虑最深层的循环是会出问题的所以分析时间复杂度和算法实现的方式有关。总之遇到分析BFS和DFS的时间复杂度时不要深入代码只需要记住算法的时间开销来自于访问顶点和找各条边即可所以可以拆开分析访问点的时间与找边的时间然后结合具体存储结构即可。
接下来看一下广度优先生成树的概念 在广度遍历的过程中可以得到一课遍历树称为广度优先生成树。
注意如果图是以邻接矩阵的方式存储因为一个图的邻接矩阵表示方式唯一广度优先遍历序列唯一因此广度优先生成树唯一。
但是如果图是以邻接表的方式存储因为一个图的邻接表的表示方式不唯一广度优先遍历序列也不唯一因此广度优先生成树不唯一。
接下来再看一个比较相近的概念广度优先生成森林 如图对于一个非连通图其上面的连通分量可以生成一个广度优先生成树下面的连通分量也可以生成一个广度优先生成树两个树合在一起就成了一个广度优先生成森林。 不难发现上面的例子都是无向图但是对于有向图广度优先算法依然成立但这里要明确一点由于有向图的边带了方向性所以对于同一图以不同的顶点为出发点调用BFS的次数不同如上图从1出发与从7出发的BFS调用次数就不相同。
下面对本节进行一个汇总 4.2 深度优先遍历 图的深度优先遍历和树的先序遍历很类似两者都使用了递归的思想可以结合学习与广度优先搜索不同这种搜索算法所遵循的策略是尽可能深地搜索一个图。如上图的例子使用深度优先搜索算法得到的序列是21563478注意考试时也可能让写深度优先搜索的遍历序列。
同广度优先搜素一样上面的算法也存在相同问题如果面对的是非连通图则无法遍历完所有结点所以也需要添加一个二次检查标记数组的函数全部代码实现如下图 接下来分析一下DFS的复杂度 空间复杂度最坏情况是如上图上面的形式的图这时候深度优先搜索需要递归深度为O(|V|)。空间复杂度最好情况是如上图下面的形式的图这时候深度优先搜索需要递归深度为O(1)。 时间复杂度分析如上分析的具体过程上图已说大体上与BFS相同有疑问可以去看一下BFS的解释再回来理解。
下面看一下深度优先遍历序列 同广度优先搜索一样根据图的表示方式不同其深度优先序列的表示也不一定唯一具体问题还需具体分析。
接下来看一下深度优先生成树的概念 与广度优先搜索一样深度优先搜索也会产生一棵深度优先生成树同样根据图的表示方式不确定深度优先生成树的唯一性也不确定。
另外连通图调用DFS才能产生深度优先生成树否则产生的将是深度优先生成森林。
接下来总结一下图的遍历与图的连通性的关系如下图 上面是无向图的遍历与连通性的关系下面看一下有向图的遍历与连通性的关系。 最后对本部分做个小结 5. 图的应用
5.1 最小生成树
5.1.1 最小生成树的概念 首先回顾一下生成树的概念如上图。图的生成树不唯一对于一个带权连通图的生成树若各边权值之和最小则称为该带权连通图的最小生成树。如下图 注意只有连通图才有生成树非连通图只有生成森林。
最小生成树的性质如下 若求一个图的最小生成树可以有两种算法分别是Prim算法和Kruskal算法。在考研初试阶段考察代码的可能性不高所以着重理解这两种算法的手动模拟过程。
5.1.2 Prim算法 上图给出了Prim算法的核心思想如果以P城为出发点则可以得到下面两个最小生成树。所以Prim算法得到的最小生成树表现形式不唯一但它一定是权值和最小的。 下面看一下Prim算法的机器实现思想 用两个数组来辅助实现Prim算法其中一个数组用来标记各节点是否已加入树另一个数组用来记录各节点加入树的最低代价。上面是初始状态以V0为出发点则V0已加入数组。同时更新各节点加入树的最低代价V4和V5由于不与V0相连所以它两无法加入树代价标位无穷。 根据最低代价数组可以发现V3加入代价最小所以先让V3加入树同时更新所有可以通过V0或V3加入树的结点的最小代价。接下来继续选择加入代价最小的点加入树如下图 往后的步骤都一样最后一组结果如下 接下来分析复杂度 每一轮循环都要选择一个新订点放入构建的树中总共有n个顶点就需要循环n-1轮而每一轮循环当中又需要经历两次遍历遍历两个数组所以每一轮复杂度为O(2n)可以舍弃常数项总共n-1轮则总时间复杂度为O(n2)。
5.1.3 Kruskal算法 上图给出了Kruskal算法的核心思想如果以P城为出发点则可以得到下图最小生成树。 下面看一下Kruskal算法的机器实现思想 Kruskal算法在初始时将图各边按照权值排序如上图右然后从第一行开始检查该边上两个点是否已经连通连通则跳过不连通则选中。下面是第一轮实现 下面是第二轮实现 按照这种方式到第五轮时出现已连通则跳过如下图 接下来按照这种方式遍历到最后最后实现的结果与Prim算法一致这里不过多阐述了。
最后看一下Kruskal的复杂度 Kruskal算法要遍历边所以要循环e轮而在每一轮过程中需要使用并查集来判断两个顶点是否属于同一集合这个判断所需时间开销为O(log2e)所以总体时间开销为O(elog2e)。
5.1.4 Prim和Kruskal比较
上面两个算法我写的比较简洁想了解具体过程的可以点击跳转链接听视频讲解最小生成树
下面看一下两种算法的时间复杂度 Prim算法每次选择顶点时间复杂度只与顶点有关为O(|V|2)。Kruskal算法每次选择边时间复杂度只与边有关为O(|E|log2|E|)。所以Prim算法适合用于稠密图Kruskal算法适合用于稀疏图。
5.2 最短路径问题 带权有向图的最短路径可以分为两类一类是单源最短路径即求图中某一顶点到其他各顶点的最短路径另一类是各顶点间的最短路径。
求单源最短路径可以使用BFS算法和Dijkstra算法BFS算法适用无权图Dijkstra适用带权图和无权图。
求各顶点间的最短路径可以使用Floyd算法Floyd算法适用于带权图和无权图。
注意这里说带权有向图的最短路径可以分为两类但后面方法中又说该方法适合无权图这里的无权图并非真正意义上的无权图而是当成各边权值为1的带权图理解也可以理解为各边权值相等的带权图此时权值意义不大。
5.2.1 BFS求无权图的单源最短路径 上面是BFS求无权图的单源最短路径的代码实现这里在原BFS的基础上多定义了数组d表示路径长度和数组path表示路径从哪个顶点过来。这里使用这两个数组的核心在于由于BFS类似树的层序遍历所以得到的数组d存储的路径长度就是最短路径。而path数组记录一每个点的前驱是为了方便找到具体的路径。
比如上面的例子从顶点2出发求顶点2与所有顶点的最短路径长度。首先要令d[2]0表示2到自己的路径为0由于刚开始所有顶点还未与顶点2连接所以所有顶点的d初始为无穷path初始为-1。第一轮BFS从2出发找到1,6则d[1]d[6]1表示1,6到2的最短路径为1这两个点的前驱都为2即path[1]path[6]2。然后以1,6为顶点使用BFS找到5,3,7由于是第二轮则5,3,7距离顶点2的长度为2但path分别指的是1,6。按照这样的方式最后得到从2出发到达所有结点的最短路径长度结果如上图。
这里有一点易错那就是数组d[ ]存的是当前结点距离出发点的最短路径而path[ ]数组存储的则是指向当前结点的上一个结点是谁。
各个顶点可以通过查找自己的前驱最终找到一条到出发点2的路径比如以结点4为例它到2的路径为4-3-6-2由于2的前驱是-1所以可以知道2就是出发点。 之前也说过通过BFS可以得到广度优先生成树不难发现对于这个生成树每个结点到底在第几层也直接反应了从起点2到达这些结点的距离到底是多少。既然BFS得到的是最短路径其实也就是说以2为根结点通过BFS得到的生成树的高度一定是最小的。
5.2.2 Dijkstra算法
BFS只适用无权图若想求带权图的某个顶点到其它顶点的最短路径就需要使用Dijkstra算法
以一个例子来看Dijkstra算法如何运行 假设现在要找到V0到其它各个顶点的最短路径如上图要初始化如图的三个数组第一个数组final表示有没有找到V0到达各个顶点的最短路径由于V0可以直达自己所以V0的标记是true。第二个数组dist表示目前为止能找到的最短路径长度V0到自己的长度为0V0能直达的是V1和V4由于别的点都未加入所以目前来看V0到V1和V4的最短路径应该是10和5而V2和V3并不存在从V0直接过来的边所以该两个点设置的值为无穷表示暂时没有找到通往该顶点的路。第三个数组path和BFS的path是一个原理这里就不再介绍目前V1和V4能确定一个比较好的路径是由V0到达所以V1和V4的path都设置为0而V0V2V4没有直接前驱就设置为-1。
进行了一系列初始化以后要进行第一轮处理从初始化的dist数组中选择dist值最小的即V4加入路径中。然后更新未加入路径的顶点的dist值和path值比如V1原来的路径长度为10但是V4连通以后可以通过V6-V4-v1的路径到达此时路径长度只有8所以更新dist[1]8path[1]4。更新完所有的顶点以后得到下图的第一轮结果。 按照上述步骤第二轮处理结果如下 第三轮处理如下 最后一轮处理如下 得到了最后的数组以后下面看一下如何处理使用数组信息 以V0到V2为例通过查dist数组可以知道V0到V2的最短路径长度为9通过查询path数组可以知道V0到V2的路径为V0-V4-V1-V2。
接下来分析一下Dijkstra算法的时间复杂度 在每一轮循环中首先要遍历所有结点找到还没确定最短路径且dist最小的顶点Vi这一步的时间复杂度为O(|V|)。找到Vi以后还要遍历与他相关的所有结点去修改dist数组和path数组。这一步的时间复杂度也为O(|V|)。也就是说每一轮的处理应是O(2|V|)但可以舍弃常数项保留下来就是O(|V|)。一共要经历n-1轮处理总的时间复杂度O(|V|2)。
Dijkstra算法和Prim算法很类似只不过Dijkstra算法的dist数组记录的是从当前顶点到某一个指定顶点的最短路径值而Prim算法的lowCost数组里记录的是某一个顶点加入到生成树里的最小代价。可以对比着学习。
最后说一下Dijkstra算法失效的例子如下图 当带权图边上带有负权值时Dijkstra算法并不使用。比如上图以V0为起点到V2最短路径应是V0-V1-V2路径长度为5但是使用Dijkstra算法得到的最短路径是V0-V2长度为7。
5.2.3 Floyd算法
写在开头我这部分写的比较简陋主要用来辅助复习的有问题可以听王道的讲解Floyd算法 Floyd算法思想如上接下来以一个例子看一下Floyd算法的过程
初始化在初始化时定义邻接矩阵A来存储带权图邻接矩阵上存储两个结点间的最短路径长度path数组存储前驱结点。在初始时不允许有任何顶点中转此时可达的两点间的最短路径就是两点间的边的权值。path数组的值全为-1。
这里注意一点邻接矩阵存储的横行代表弧的射出竖行代表弧的射入。 初始化以后现在允许V0为中转检查每两个顶点间的路径是否可以通过V0中转可以的话路径长度为多少与原来相比是大是小如果小则更新最短路径如果大则保持原来路径。允许V0为中转的两个数组的更新如下 接下来允许V0V1为中转检查每两个顶点间的路径是否可以通过V0V1中转可以的话路径长度为多少与原来相比是大是小如果小则更新最短路径如果大则保持原来路径。允许V0V1为中转的两个数组的更新如下 接下来允许V0V1V2为中转检查每两个顶点间的路径是否可以通过V0V1V2中转可以的话路径长度为多少与原来相比是大是小如果小则更新最短路径如果大则保持原来路径。允许V0V1V2为中转的两个数组的更新如下 经过上面三轮迭代我们已经把所有结点都考虑进去此时得到的数组就是最终的数组A数组里存储了图中任意两点间的最短路径长度path数组存储了在最短路径中每个点的前驱。对于最终数组的具体分析与使用可以参考下图 这里补充一点在Floyd算法里有n个顶点在初始化以后就要经历n轮更新迭代。
Floyd算法的代码实现如下 根据上图很清晰的可以看到时间复杂度为O(|V|3)空间复杂度为O(|V|2)。
最后看一下啊Floyd算法无法处理的情况
首先再看一下负权图上面我们说Dijkstra算法无法用于负权图所以可以尝试用Floyd算法模拟负权图最后会发现Floyd算法是可以用于负权图的。 但是Floyd算法也有无法实现的情况比如下面负权回路图因为这种图有可能没有最短路径所以Floyd算法也无法求出最短路径。 下面对三个求最短路径问题的方法进行小结 5.3 有向无环图描述表达式
先看一下什么是有向无环图如下图 知道了什么是有无环图接下来就是本部分重点用有向无环图来描述表达式。 之前的学习说过算术表达式可以用树的形式来表示如上图但仔细观察会发现树中存在重复的部分比如上图的红色部分和绿色部分这时候可以采用有向无环图实现对相同子式的共享从而节省存储空间。所以可以将其合并成如下图的形式 注意这个树依然有许多相同的部分所以我们可以将其全部合并最后合并的结果如下图 最后合并出来的结果就是该表达式的有向无环图表示。
这部分的题很简单多数都是考察有向无环图描述表达式需要的顶点个数或绘制有向无环图。但是由于要合并的点可能有很多导致做题时可能出现遗漏所以下面提供一种做题方法 按照图中步骤先构造出如图的表示形式然后执行第四步自底向上逐层检查同层的运算符是否可以合并若可以就合并最后得到就是有向无环图的描述表达式如下图 5.4 拓扑排序
先看一下什么是AOV网 所谓AOV网就是用有向无环图表示一个过程顶点表示活动用有向边Vi,Vj表示活动Vi必须先于活动Vj进行的这样一种关系则将这种有向图称为顶点表示活动的网络称为AOV网。
了解AOV网以后接下来看一下拓扑排序的概念。 简单的理解拓扑排序就是AOV网里找到做事的先后顺序。
如上图的番茄炒蛋AOV网拓扑排序的顺序就可以为买菜、准备厨具、洗番茄、切番茄、打鸡蛋、下锅炒、吃。当然也可以排序为准备厨具、买菜、洗番茄、切番茄、打鸡蛋、下锅炒、吃。除了这两种还有其它的排序方式所以每个AOV网的拓扑排序序列不唯一。
下面看一下拓扑排序的实现步骤 需要注意并不是所有的图都可以进行拓扑排序比如存在回路的图就无法进行拓扑排序如下图 接下来看一下拓扑排序的代码实现拓扑排序的代码实现就是将前面所说的拓扑排序的实现步骤用代码的形式表示出来 上图是拓扑排序的代码实现右边的才是拓扑排序的代码左边的是存储结构的描述与定义注意这里使用邻接表来存储图。
下面重点看拓扑排序的代码部分 拓扑排序的代码先声明图中代码没有声明了两个数组indegree[ ]和print[ ]分别用来记录当前顶点的入度和拓扑排序序列。此外还定义了一个栈用来存储入度为0的点。
下面看一下代码实现的过程首先由于未开始排序所以print数组全部初始化为-1。代码里第一个for循环会检查所有入度为0的点并将入度为0的点放入栈中保存上例中会把0和2依次压入栈中。接下来用count记录当前已输出的顶点数由于栈里先弹出2号顶点所以count指向位置存出2表示拓扑序列里第一个值为2。接下来的for循环把所有与2相连的结点入度减1此时与2相连的点没有入度变成0的所以不需要再次入栈。到此为止完成第一轮循环。
接下来由于栈里还有顶点0所以栈非空要进行第二轮while循环。同顶点2的操作一样但是到最后将0出栈实现与0相连的结点入度减1时出现1结点入度为0所以要把1入度。到此完成第二轮循环。
第三轮由于栈里有顶点1还要接着进入while循环按照这种方式继续迭代当出现栈空时则跳出循环。
跳出循环的情况有两种一是出现回路一是拓扑排序成功判断是回路还是排序成功的方式是通过比较已被排序的顶点个数和顶点总个数若相等则排序成功若不等则存在回路。
接下来分析时间复杂度 由于代码执行过程中每个顶点都需要处理一次每个边也都需要处理一次所以时间复杂度为O(|V||E|)。但是要采用邻接矩阵存储遍历每条边则要访问整个邻接矩阵时间复杂度为O(|V|2)。
接下来看逆拓扑排序与拓扑排序很像只不过逆拓扑排序是选择出度为0的顶点输出。 上图的逆拓扑排序序列就可以为吃、下锅炒、切番茄、洗番茄、打鸡蛋、准备厨具、买菜。
下面看一下逆拓扑排序的实现 上图给出的是拓扑排序的实现代码要想改成逆拓扑排序首先需要将拓扑排序里每次将入度为0的点删去改成每次将出度为0的点删去然后要根据所使用的存储结构来进行程序设计。
这里要考虑一下存储结构对逆拓扑排序时间复杂度的影响当实现逆拓扑排序时由于要找每个点的入度此时使用邻接表法就不太合适所以采用邻接矩阵法可以稍微好一点。除了这两种这里再补充一个逆邻接表法即每个顶点后面跟的是指向自己的点如果采用逆邻接表存储实现逆拓扑排序就会更加方便。
在考试时还喜欢出用DFS实现拓扑排序和逆拓扑排序下面是DFS实现按逆拓扑排序的方法 用DFS实现逆拓扑排序的核心就是将被访问完所有邻接点的顶点输出。比如说上面的例子用栈来存储被访问的顶点每一个被访问的顶点就做上标记并压入栈中。当访问到没有邻接点的时候就意味着访问到最后一个顶点此时就要进行出栈操作在每一个顶点出栈前将顶点输出就构成了逆拓扑排序序列。另外DFS可能会出现同级点没有被访问的情况如上图在进行完一次DFS后还要检查是否所有点都被访问若存在未被访问的要二次调用DFS。上图经过上述步骤最后输出逆拓扑排序序列43102。
补充DFS实现拓扑排序
// 假设图使用邻接表表示
#define MAX_VERTICES 100 // 最大顶点数 typedef struct Node { int vertex; struct Node* next;
} Node; typedef struct Graph { int numVertices; Node** adjLists; // 邻接表 int* visited; // 标记顶点是否被访问过 int* finishTime; // 顶点的完成时间逆后序遍历顺序
} Graph; // 创建一个新节点
Node* createNode(int vertex) { Node* newNode (Node*)malloc(sizeof(Node)); newNode-vertex vertex; newNode-next NULL; return newNode;
} // 添加边到图的邻接表
void addEdge(Graph* graph, int src, int dest) { Node* newNode createNode(dest); newNode-next graph-adjLists[src]; graph-adjLists[src] newNode;
} // DFS遍历并计算完成时间
void DFS(Graph* graph, int vertex, int* stack) { graph-visited[vertex] 1; Node* temp graph-adjLists[vertex]; while (temp) { if (!graph-visited[temp-vertex]) { DFS(graph, temp-vertex, stack); } temp temp-next; } // 将当前顶点压入栈中以获取逆后序遍历完成时间 stack[graph-numVertices - 1 - graph-finishTime[vertex]] vertex;
} // 拓扑排序函数
void topologicalSort(Graph* graph) { graph-visited (int*)calloc(graph-numVertices, sizeof(int)); graph-finishTime (int*)calloc(graph-numVertices, sizeof(int)); int* stack (int*)malloc(graph-numVertices * sizeof(int)); // 初始化完成时间数组 for (int i 0; i graph-numVertices; i) { graph-finishTime[i] graph-numVertices; } // DFS遍历每个未访问过的节点 for (int i 0; i graph-numVertices; i) { if (!graph-visited[i]) { DFS(graph, i, stack); } } // 栈中存储的是逆后序遍历出栈则为拓扑排序 printf(拓扑排序结果: ); for (int i 0; i graph-numVertices; i) { printf(%d , stack[i]); } printf(\n); free(graph-visited); free(graph-finishTime); free(stack);
} 下面思考一个问题对于上面的DFS实现逆拓扑排序如果存在回路则无法进行逆拓扑排序这里怎么判断有回路存在
我的想法是可以使用“递归”和“访问标记”的方法。当一个节点在递归过程中被第二次访问即它不是当前递归路径的父节点那么图中就存在回路。这是我的想法答案应该不唯一能实现就行。
最后对拓扑排序内容进行小结 5.5 关键路径
首先看一下什么是AOE网 与AOV网不同AOE网用顶点表示事件用有向边表示活动以边上的权值表示完成该活动的开销。
AOE网具有两条性质
只有某顶点所代表的事件发生后从该顶点出发的各有向边所代表的活动才能开始。只有在进入某顶点的各有向边所代表的活动都已结束时该顶点所代表的事件才能发生。但是要注意如果一个顶点后面有多个事件则这些事件是可以并行的。
接下来看一下源点和汇点的概念 AOE网中只有一个入度为0的顶点称为开始顶点也叫源点。也仅有一个出度为0的顶点称为结束顶点也叫汇点。
到这里就可以引出关键路径与关键活动的概念 从源点到汇点的所有有向路径里具有最大路径长度的路径称为关键路径而把关键路径上的活动称为关键活动。到这里就可以知道完成某个工程的最短时间就是关键路径长度若有关键活动不能按时完成则整个工程的完成时间就会推迟。
为了求关键路径与关键活动需要先引入几个概念
(1) 事件的最早发生时间与活动的最早开始时间。 (2) 事件的最吃发生时间与活动的晚早开始时间。 (3) 时间余量。 将活动的最早开始时间与最迟开始时间放到一起可以发现当一个活动的最早开始时间与最迟开始时间相等时活动就不可以拖延若最早开始时间小于最迟开始时间则两者的差值就是活动可以拖延的时间。如上图的打鸡蛋步骤就可以推出2分钟开始。
我们将活动最迟开始时间与活动最早开始时间的差值叫做活动的时间余量。时间余量表示在不推迟工程完成时间的情况下某个活动可以拖延的时间。
了解了这些概念就可以将关键路径的计算步骤总结如下
求关键路径的步骤可以总结为先求出事件的最早和最迟发生时间进而可以求得活动的最早和最迟发生时间最后计算活动余量。活动余量为0的就是关键活动所有关键活动就构成了关键路径。
下面分别看一下这些步骤的实现这部分呢比较简单我直接贴个图有重点会说一下
(1) 求所有事件的最早发生时间。 (2) 求所有事件的最晚发生时间。 (3) 求所有活动的最早发生时间。 (4) 求所有活动的最晚发生时间。 (5) 求时间余量。 求出了时间余量就可以将所有时间余量为0的活动组合起来就构成了关键路径如图。
接下来说一下关键活动与关键路径的特性 关键活动决定着整个工程工期如果关键活动耗时增加则整个工程的工期将增长所以可以缩短关键活动的时间进而缩短整个工程的工期。但是当关键活动缩短到一定程度时可能会出现其他活动的耗时超过这个关键活动此时关键活动就变成了非关键活动再缩短时间也不会影响工期。
另外由于AOV网可能存在多条路径所以可能出现下面的情况即存在两天时间相等的最长路径则这两条路径都是关键路径此时缩短其中一条活动的时间并不一定能缩短整体工期只有加快那些包括在所有关键路径上的关键活动才能缩短工期。如下图缩短打鸡蛋并不能缩短活动的工期但缩短所有关节路径都包含的炒菜就可以缩短工期。 最后对关键路径进行小结
.png
(3) 求所有活动的最早发生时间。 (4) 求所有活动的最晚发生时间。 (5) 求时间余量。 求出了时间余量就可以将所有时间余量为0的活动组合起来就构成了关键路径如图。
接下来说一下关键活动与关键路径的特性 关键活动决定着整个工程工期如果关键活动耗时增加则整个工程的工期将增长所以可以缩短关键活动的时间进而缩短整个工程的工期。但是当关键活动缩短到一定程度时可能会出现其他活动的耗时超过这个关键活动此时关键活动就变成了非关键活动再缩短时间也不会影响工期。
另外由于AOV网可能存在多条路径所以可能出现下面的情况即存在两天时间相等的最长路径则这两条路径都是关键路径此时缩短其中一条活动的时间并不一定能缩短整体工期只有加快那些包括在所有关键路径上的关键活动才能缩短工期。如下图缩短打鸡蛋并不能缩短活动的工期但缩短所有关节路径都包含的炒菜就可以缩短工期。 最后对关键路径进行小结 写在最后该系列笔记是本人在25考研备考408过程中根据王道课程所整理的复习笔记原本放在个人网站方便自己复习所用。现考完以后为了给个人网站减负故将其全部移植到CSDN上。笔记中会存在一些错别字和输入法错误不过考完以后实在不想再去纠错所以欢迎大家在评论区中指出博主看到以后会进行纠正。
