数据结构-Maple Related-牟克典牟克典数学科学学院信息科学系数学科学学院信息科学系20122012秋季秋季9/2/20241第五讲第五讲 图和图算法图和图算法(1)(1)图：基本概念和性质图的基本操作图的遍历宽度优先深度优先图的表示生成树最小生成树20122012年年1111月月2121日日10:10-12:0010:10-12:00三教三教3033039/2/20242图（graph）图是一种数学结构，数学里有分支 “图论”，研究一种拓扑结构这里把它看着一类复杂数据结构，用于表示具有各种复杂关系的数据集合。图在实际中应用很广泛本章介绍图的最基本知识，图的基本实现方法，以及图的若干最基本的计算问题和重要算法重点算法（这些算法是本章最重要的内容）：图的深度优先搜索与广度优先搜索最小生成树的 Prim 算法和 Kruskal 算法求单源最短路径的 Dijkstra 算法求所有顶点对之间最短路径的 Floyd 算法拓扑排序关键路径9/2/20243图：基本概念图图是二元组 G = ( V, E )，其中V 是顶点的非空有穷集合（可有空图的概念，用处不大）E 是顶点偶对 (称为“边”) 的集合，E VVV 中的顶点也称为图 G 的顶点，E 中的边也称为图 G 的边有向图有向图：有向图中的边有方向，边是顶点的有序对有序对用尖括号表示。 表示从 vi 到 vj 的有向边，vi 称为边的始点，vj 是边的终点。 和 表示两条不同有向边无向图无向图：无向图中的边没有方向，是顶点的无序对无序对用圆括号表示，(vi , vj) 和 (vj , vi) 表示同一条无向边如果图 G 里有边 E 或者 (vi, vj) E 顶点 vj 称为 vi 的邻接顶点邻接顶点（对无向图，邻接点是双向的）这种边称为与顶点 vi 相关联的边相关联的边或 vi 的邻接边邻接边与有序树类似，图中的邻接边也可以规定顺序9/2/20244图图可用图形自然表示（圆圈表示顶点，线段或箭头表示边）v1v2v3G1v1v4v3v3G2v1v2v3v7v6v5v4G3两个限制：1）不考虑顶点到自身的边，若 (vi ,vj) 或 是 G 的边，则要求 vi vj；2）顶点间没有重复出现的边，若 (vi ,vj) 或 是 G 的边，则它是这两个顶点间的唯一边（不存在多重边）去掉这些限制得到稍微不同的数学研究对象。图论中也研究它们9/2/20245图：概念和性质完全图完全图：任意两个顶点之间都有边的图（有向图或无向图）。显然：n 个顶点的无向完全图有 n*(n-1)/2 条边n 个顶点的有向完全图有 n*(n-1) 条边注意图上的重要事实：|E| |V|2，或者 |E| O( |V|2 )度度（顶点的度）：与一个顶点关联的边的个数。对于有向图，还分为出度出度和入度入度，分别表示以该顶点为始点或者终点的边的个数无论是有向图还是无向图，顶点数 n，边数 e 和度数满足下面关系:其中 D(vi) 表示 vi 的度数9/2/20246路径和相关概念路径路径：对图 G = (V, E)，若存在顶点序列 vi0,vi1,vi(m)，使 (vi0,vi1)，(vi1,vi2), (vi(m-1), vi(m) 都在 E 中（对有向图 , , , 都在 E 中)则说从顶点vi0到vi(m) 存在一条路径 称为从 vi0 到 vi(m) 的路径路径长度路径长度：路径上边的条数回路回路（环环）：起点和终点相同的路径如果除起点和终点外的其他顶点均不相同，则称为简单回路简单回路简单路径简单路径：内部不包含环路的路径，即，路径上的顶点除起点和终点可能相同外，其它顶点均不相同简单回路也是简单路径9/2/20247子图、有根图对图 G = (V，E) 和 G = (V，E)，如果 V V 且 E E，就称 G 是 G 的子图子图。特别的，G 是其自身的子图下面是有向图G1的几个子图G1 v1v1v1 v2v2v2v2 v3v1 v2v3有根图有根图q如果有向图 G 中存在一个顶点 v，从 v 有路径可以到达图 G 中其它所有顶点，则称 G 为一个有根图，v 称为图 G 的一个根q有根图中的根可能不唯一9/2/20248连通图连通连通：如果无向图 G 中存在从 vi 到 vj 的路径（显然它也是从 vj到 vi 的路径)，则称 vi 与 vj 连通（默认顶点 v 到自身连通）无向图的连通性连通图连通图：如果无向图 G 中的任意两个不同顶点 vi 和 vj 之间都连通（都存在路径），则称 G 为连通图极大连通子图极大连通子图是图中极大的连通子图（没有真包含它连通子图）连通分量连通分量：无向图 G 的一个极大连通子图称为 G 的一个连通分量。若 G 不连通，其连通分量将多于一个，它们形成 G 的一个划分划分有向图的连通性强连通图强连通图：如果有向图 G 中任意两个不同顶点 vi 和 vj 之间都存在从 vi 到 vj 以及从 vj 和 vi 的路径，则称 G 是一个强连通图强连通分量强连通分量：有向图G的极大强连通子图称为它的强连通分量有向图 G 的强连通分量形成其顶点的一个划分顶点的一个划分9/2/20249带权图和网络若图 G 的每条边都被赋以一个权值，G 称为是带权图权值可用于表示实际应用中与顶点关联有关的某种量带权的连通无向图称为网络网络下图为一个网络网络是实际应用非常广泛的一类图结构后面会介绍网络上的一些重要性质和算法、以及它们的应用9/2/202410图的基本操作作为复杂的数据结构，图上可能定义许多操作。下面列举一些操作创建空图，判断图 g 是否空图，把图 g 置为空图：createGraph ( )createGraph ( ) isEmptyGraph ( g ) isEmptyGraph ( g ) clearGraph ( g clearGraph ( g ) )图中顶点个数（order）和边个数（size）order( g ) order( g ) size( g )size( g )图中所有顶点的集合，所有边的集合：vertices ( g )vertices ( g )edges( g )edges( g )图 g 中顶点 v 的入度和出度（结果用二元序列表示）：vdeg ( g , v )vdeg ( g , v )在图 g 中增加一条边 或 (v1,v2)：addEdge ( g , v1 , v2 )addEdge ( g , v1 , v2 )9/2/202411图的基本操作检查图 g 中是否存在边 或 (v1,v2)： findEdge findEdge ( g , v1 , v2 )( g , v1 , v2 )在图 g 中删除边 或 (v1,v2)： deleteEdge deleteEdge ( g , v1 , v2 )( g , v1 , v2 )找出图 g 中与顶点 v 相邻的顶点（集合或表）： adjacentVertices adjacentVertices ( g , v )( g , v )在图 g 中删除一顶点和与之关联的所有边： deleteVertex deleteVertex ( g , v )( g , v )图中的遍历操作图中的遍历操作。与树遍历的关键差异包括：要防止走到已遍历过的部分要考虑图的连通性问题（图可能不连通，遍历完一个连通分支后还不能结束，需要去遍历其他分支）9/2/202412图的遍历图的遍历图的遍历按某种方式系统访问图中所有顶点，且每个顶点仅访问一次的过程也称为图的周游遍历的基本部分是访问一个顶点所在的连通分支（对有向图，强连通分支）的全部顶点。如果不是连通图，还需要访问其他连通分支基本的图遍历方法同样是：深度优先遍历深度优先遍历（通过深度优先搜索的方式遍历）广度优先遍历广度优先遍历（通过广度优先搜索的方式遍历）两种方式对有向图和无向图都适用9/2/202413深度优先遍历深度优先遍历 (Depth-First Traversal) 的策略就是按照深度优先搜索（Depth-First Search）的方式遍历，做法是：从指定顶点 v 出发，先访问 v 并将其标记为已访问依次依次从 v 的未访问过的各邻接顶点 w 出发进行深度优先搜索（要取得 v 的邻接顶点，可能排列一种顺序），直到图中与 v 连通的所有顶点都访问过（递归）如果图中还有未访问顶点，则选一个未访问顶点，由它出发重复上述过程，直到图中所有顶点都已访问为止对图进行深度优先遍历，按访问顶点的先后次序得到的顶点序列，称为该图的深度优先搜索序列深度优先搜索序列（ Depth-First Search 序列），通常简称为 DFS DFS 序列序列由于遍历中邻接点通常有多个，对它们的不同（递归）访问顺序将得到不同的 DFS 序列（不唯一）如果规定了图中个顶点的邻接点顺序，DFS 序列就确定了9/2/202414深度优先遍历一个简单示例：V7V6V3V2V5V1V8V4假定各顶点的邻接顶点从左到右排序，得到的 DFS 序列：9/2/202415深度优先遍历算法这个示意算法说明了 DFS 的过程，基本部分是遍历一个连通分支DFTGraph := proc(g:Graph) while existUnvisited(g) do DFSComponent(g, nextUnvisited(g) odend:DFSComponent := proc(g, v) local adjs, va; visit(v); markVisited(v); adjs := adjacentVertices (g, v); for va in adjs do if unvisited(va) then DFSComponent(g, va) fi odend:9/2/202416广度优先遍历广度优先遍历 (Breadth-First Traversal) 的遍历方式是通过广度优先搜索（Breadth-First Search），具体过程是：从指定顶点 v 出发，先访问顶点 v 并将其标记为已访问依次访问 v 的所有相邻顶点 v1, v2, , vm （可以为 v 的邻接顶点假定一种顺序） ，然后依次访问与 v1, v2, , vm 邻接的所有未访问顶点（递归）直到所有已访问顶点的相邻顶点都已访问为止如果图中还有未访问顶点，则选择一个未访问顶点，由它出发进行广度优先搜索，直到所有顶点都已访问为止通过广度优先遍历得到的顶点序列称为图中顶点的广度优先搜索序列（ Breadth-First Search 序列）或BFS序列由于遍历中邻接点通常有多个，对它们的不同（递归）访问顺序将得到不同的 BFS 序列（不唯一）如果规定了图中各顶点的邻接点顺序，BFS 序列就确定了9/2/202417广度优先遍历简单示例：V7V6V3V2V5V1V8V4假定各顶点的邻接顶点从左到右排序，得到的 BFS 序列：9/2/202418广度优先遍历BFTGraph := proc(g:Graph) while existUnvisited(g) do BFSComponent(g, nextUnvisited(g) odend:BFSComponent := proc(g, v) local vq, va, adjs; vq := queuenew(v); while not queueempty(vq) do v := queuedequeue(vq); visit(v); markVisited(v); adjs := adjacentVertices (g, v); for va in adjs do if unvisited(va) then queueenqueue(va) fi od odend:9/2/202419图的表示图的结构比较复杂，任意两个顶点间都可能存在边需要表示顶点及顶点间的边，存储方法很多应根据具体应用和需要做的操作，选择图的存储表示法图的最基本表示方法是邻接矩阵表示法最基本表示方法是邻接矩阵表示法表示图的邻接矩阵通常非常稀疏。很多图中边的个数与顶点个数成线性关系，如中国铁路线路图人们提出了其他表示方法，都可看着邻接矩阵的“压缩”版本直接邻接矩阵存储空间可能浪费较大，人们考虑了各种变形，如：邻接表表示法邻接多重表表示法图的十字链表，等下面只介绍邻接表表示法9/2/202420图的表示：邻接矩阵邻接矩阵是一个矩阵，其中表示了图中顶点间的邻接关系设 G = (V，E) 为 n 个顶点的图，其邻接矩阵为如下 n 阶方阵：=不是图 G 的边或若是图 G 的边或若vvvvvvvvjiAjijijiji,),(0,),(1,邻接矩阵只表示了图中顶点个数和顶点间的联系（边）每个顶点对应一个矩阵下标可通过一对下标确定图中一条边的有无如果顶点本身还有其他信息，就需要用另外的方式表示顶点例如，可以考虑另外用一个顶点表用与矩阵同样下标引用同一顶点的表元素9/2/202421邻接矩阵：示例下面无向图 G1 和有向图 G2 的邻接矩阵分别为 A1 和 A2=00110011110111101A=01000000010101010001000102A9/2/202422带权图带权图的边包含有用的信息，采用邻接矩阵表示时可以把权信息记录在矩阵里。矩阵元素是边的权值，无边的情况另行表示设 G 是带权图，wij 是边 (vi,vj) 或 的权，图 G 的邻接矩阵定义为（用邻接矩阵元素记录边的权）：=或若或或若vvvvvvvvwjiAjijijijiij,),(0,),(,不是图G的边是图G的边下面带权图的两个邻接矩阵分别为A3和A4，根据需要用 0 或表示无边=010011010024802065114603085303A=101110248265114638534A9/2/202423在 Maple 里实现邻接矩阵在 Maple 里用邻接矩阵方法实现图，内部表示可以用两个成分：一个 n 元素的一维 Array 存储顶点信息一个 nn 的二维 Array 表示邻接矩阵这种表示需要首先确定图中顶点个数。可以加入/删除边，但顶点的情况固定了采用这种实现，操作和空间利用效率高，但灵活性稍差另一种可能设计是利用 Maple 的 table用两个 table 分别存储邻接矩阵和顶点信息给每个顶点一个标识（整数或者唯一名字），用这种标识建立两部分信息之间的联系这种表示可以支持任意的顶点/边加入和删除这种表示实际是利用 Maple 的 table 机制（散列表，后面介绍）的灵活性，操作效率通常也比较高，但可能占用的空间大些9/2/202424邻接表表示法邻接表表示的形式与树的“子表表示”相同，用一个顶点表表示图中顶点信息每个顶点关联一个邻接表，记录与之相关的邻接顶点无向图：一个顶点表，每个顶点有一个关联边的表边 (vi,vj) 在顶点 vi，vj 的边表各有一结点，在边表中存储两次顶点 vi 的边表中结点个数为顶点 vi 的度v1v2v3v4211133224412349/2/202425邻接表表示法 有向图有向图一个顶点表，每个顶点关联一个边表顶点 vi 的边表中每个结点对应的是以 vi 为始点的一条边，因此，将有向图邻接表的边表称为出边表出边表顶点 vi 的边表中结点个数为顶点 vi 的出度也可采用入边的表，表中结点个数是顶点的入度v1v2v3v4411341234 v1v4 v2v3出边表出边表9/2/202426邻接表表示法v1v2v3v421215v1v2v3v52134352v4v544存储出边表的情况存储入边表的情况9/2/202427生成树生成树生成树的概念从连通无向图或强连通有向图 G 中的任一顶点 v0 出发，或从有根有向图的根 v0 出发，存在到图中其他各结点的路径若 G 有 n 个顶点，必然可找到 n-1 条边，其中包含了从 v0 到其他所有结点的路径（很容易通过数学归纳法证明）。这样的 n-1 条边形成 G 的一个子图 T（包含 G 所有顶点和 n-1 条边）对无向图 G，这样的子图 T 是一个最小连通子图（去掉任意一条边后不再连通）。n 个顶点 n-1 条边的图成树形，因此称子图 T 为 G 的生成生成树树。对有向图的定义类似。图的生成树可能不唯一性质性质：n 个顶点的连通图的生成树包含恰好 n-1 条边无向“树”就是连通的无环图。有向“树”的边都位于从根到其他结点的（有方向的）路径上非连通的无向图可划分为一组连通分量，可以定义它们的生成树林生成树林n 个顶点 m 个连通分量的图 G 的生成森林恰好包含 n-mn-m 条边9/2/202428遍历和生成树从连通无向图或强连通有向图中任一顶点出发遍历，或从有根有向图的根顶点出发遍历，都可以访问到所有顶点遍历经过的边加上所有顶点，就构成该图的一棵生成树遍历经过的边加上所有顶点，就构成该图的一棵生成树构造生成树的过程可以按深度优先遍历或广度优先遍历遍历中记录访问的所有顶点和经过的边，就得到深度优先生成树，或广度优先生成树，简称为 DFS DFS 生成树生成树或 BFS BFS 生成树生成树无向图DFS生成树BFS生成树9/2/202429遍历生成树也可把连通无向图的生成树定义为包含其全部顶点的最小连通子图，一般无向图的生成树林定义为各连通分量的最小连通子图的集合也可以把强连通有向图的生成树定义为包含了其全部顶点的最小有根子图最小有根子图（有向树，去掉一条边就不是有根图了）生成树描述了图的一种框架结构，也称为支撑树支撑树有向图的遍历产生的生成树9/2/202430最小生成树网络 G（带权连通无向图）的边带有权值，其生成树中各条边的权值之和称为该生成树的权生成树的权网络 G 可能有多棵不同生成树，其权值可能不同。其中权值最小的生成树称为 G 的最小生成树最小生成树 (Minimum Spanning Tree，MST)最小生成树可能不唯一最小生成树有许多实际应用：把网络顶点看作城市，边的权看作连接城市的通讯线路成本。根据最小生成树建立的是城市间成本最低的通讯网可类似考虑成本最低的公路网等农村村庄之间的输电网络、有线电视网输水管线、暖气管线、配送中心与线路的规划集成电路或印刷电路版的地线，供电线路等等9/2/202431最小生成树：MST 性质MST 性质：设 G = (V，E) 是网络，U 是V 的任一真子集，e = (u,v) E，其中 uU，vV - U，而且 在 G 中所有一端点在 U 另一端点在 V - U 的边中e的权值最小G G 必有一棵包括边必有一棵包括边 e e 的最小生成树的最小生成树（网络总有最小生成树）MST 性质的证明：任取 G 的一棵最小生成树T，T 中必有一条一端在 U 另一端在 V-U 的边，设为 e。T 加上 e 得到一个包含环路的图，去掉 e 得到另一生成树，其权值不大于 T，因此是最小生成树UV - U图 Gee9/2/202432最小生成树：Prim 算法基本思想是从一个顶点出发，直接利用 MST 性质逐渐扩充已连接顶点集合，直至集合中包含了所有顶点；或最终确定不是连接图算法细节：从图 G 的顶点集 V 中任取一顶点 (例如取顶点v1) 放入集合 U 中，这时 U = v1，边集合 TE = ，T = (U, TE) 是树检查所有一个顶点在集合 U 里另一顶点在集合 V U 的边，找出其中权值最小的边 e = (u, v)（uU，vV-U），将顶点 v 加入集合 U，并将 e 加入 TE。(U, TE) 仍是一棵树重复上面步骤，直至 U = V（树中包含所有顶点）。这时 TE 有 n-1条边，T = (U, TE) 就是 G 的一棵最小生成树这个算法直接利用 MST 性质构造最小生成树算法的正确性：这一算法最后得到的必然是 G 的最小生成树请考虑如何证明这个算法的正确性9/2/202433Prim 算法示例9/2/202434Prim 算法实现的思想已知图 G 图采用邻接矩阵表示，构造该图的最小生成树使用的数据表示：用顶点对的下标 (在顶点表中的下标) 表示边。例如：1, 2, 10 1, 2, 10 表示顶点表示顶点 1 1 到顶点到顶点 2 2 的边上的权为的边上的权为 10 10用一个 n-1 元的数组 mstmst（n为顶点数），其中保存一组边算法开始时设想 v1 在最小生成树的顶点集 U 里，mst 里记录从 v1 到其余顶点的最短边（都是最短边）和权（无边时权值看作无穷）算法执行中反复选择当时 mst 里与 U 中顶点之间的边中权值最小的另一顶点加入 U，同时更新 mst 里记录的到其他顶点的边和权，使 mst 始终记录从 U 到其他顶点的最短边和权具体方法是让 mst 前段记录已知属于最小生成树的边，后面记录 U 到不属于 U 的顶点的最小权的边算法结束时 mst 中存放着最小生成树的n-1条边9/2/202435Prim 算法实现梗概算法实现梗概：开始时只有 v1 属于最小生成树 T 的结点集 U，将 mst 初始化为从 v1 到其他各顶点的边和权值，无边时权值取无穷大。在 Maple 里无穷大用 infinity 表示，设邻接矩阵中无边也用 infinity 表示循环 n-1 次，向 T 加入 n-1 个顶点和相关边（在第 i 次检查循环条件时，mst1 . mst i-1 记录了属于U的边和结点）找出关联到 U 之外的顶点的最短边把该边和关联点加入 T（把相关边与mst i 交换位置）检查新顶点 vi 与 U 之外的顶点之间边的权值，如果它比 mst 中记录的到那个顶点的边的权值小，就用 vi 到那个顶点的边代替 mst 里原记录的相关边将 n-1 个顶点与边加入后，算法结束如 mst 里剩下的边权都是无穷大，那么图不连通，无最小生成树9/2/202436Prim 算法运行情况例：已知下面图 G 及其邻接矩阵，构造该图的最小生成树03314112133018191418066605116501021191001、n = 6。开始时只有顶点v1在最小生成树中。mst = 1,2,10, 1,3, 1,4, 1,5,19, 1,6,21 2、在 mst1 到 mst5 中找出权值最小的边 mst1，即 (v1, v2)，将顶点 v2 及边 (v1, v2) 加入最小生成树。而后考虑是否要替换一些点的“已知最近路径”9/2/202437Prim 算法运行情况03314112133018191418066605116501021191003、考虑 mst2 到 mst5 和 v2 的边(v2, v3) = 5 小于(v1, v3)替换(v2, v4) = 6 小于(v1, v4)替换(v2, v5) = 大于(v1, v5)不变(v2, v6) = 11 小于(v1, v6)替换mst = 1,2,10, 2,3,5, 2,4,6, 1,5,19, 2,6,11 红色表示已知在最小生成树中的边4、在 mst2 到 mst5 找出权值最小的边 mst2，即 (v2, v3)，将顶点v3和边(v2, v3)加入最小生成树9/2/202438Prim 算法运行情况5、考虑 mst3 到 mst5(v3, v4) = 6 不小于 (v2, v4) 不变(v3, v5) = 大于 (v1, v5)不变(v3, v6) = 大于 (v2, v6)不变mst = 1,2,10, 2,3,5, 2,4,6, 1,5,19, 2,6,11 6、在 mst3 到 mst5 中找出权值最小的边 mst3，即 (v2, v4)，将顶点 v4 及边 (v2, v4) 加入最小生成树03314112133018191418066605116501021191009/2/202439Prim 算法运行情况03314112133018191418066605116501021191007、考虑 mst4 到 mst5(v4, v5) = 18 小于(v1, v5)调整(v4, v6) = 14 大于(v2, v6)不变mst = 1,2,10, 2,3,5, 2,4,6, 4,5,18, 2,6,11 8、在 mst4 到 mst5 中找出权值最小的边 mst5，即(v2, v6)，将顶点 v6 及边 (v2, v6) 加入最小生成树。互换 mst4 和 mst5，得到 mst = 1,2,10, 2,3,5, 2,4,6, 2,6,11, 4,5,18 9/2/202440Prim 算法运行情况03314112133018191418066605116501021191009、考虑调整 mst4(v6, v5) = 33 大于 (v4, v5)不变mst = 1,2,10, 2,3,5, 2,4,6, 2,6,11, 4,5,18 10、将 mst5 加入最小生成树。mst = 1,2,10, 2,3,5, 2,4,6, 2,6,11, 4,5,18 9/2/202441Prim 算法的 Maple 描述prim := proc(vmun, adjMat) local i, j, weight, mn, tmp, vx, vy, mst; mst := Array(1.vnum-1); for i from 1 to vnum - 1 do #初始化数组初始化数组 mst msti := 1, i+1, abjMat1,i+1 od; for i from 1 to vnum - 1 do mn := i; weight := msti3; for j from i+1 to vnum-1 do #找出分界边中最短的边找出分界边中最短的边 if evalb(mstj3 weight) then mn := j; weight := mstj3 fi od; tmp := mstmn; mstmn := msti; msti := tmp; vx := msti2; #新加入边的终点新加入边的终点 for j from i+1 to vnum-1 do #检查是否需要替换边检查是否需要替换边 vy := mstj2; weight := adjMatvx,vy; if evalb(weight mstj3) then mstj := vx, vy, weight fi od odend:9/2/202442Prim 算法的复杂性分析Prim算法的时间主要用在选择最小生成树的 n-1 条边和选择后检查和替换边时。外循环执行 n-1 次，包含两个内循环，时间耗费为：算法的时间复杂度是 O(|V|2)算法的空间复杂度：算法中主要就是用了一个数组 mst该数组的大小正比与顶点个数由此算法的空间复杂度是 O(|V|)应该觉得这一算法有可能改进。关键操作（也是提高效率的关键）q找出分界边中最短的边q检查是否需要更新分界边9/2/202443Prim 算法的复杂性分析采用不同辅助数据结构，可使 Prim算法的复杂度变为 O(|E| log |V|)，其中 |E| 和 |V| 是边集合和结点集合的大小。在边比较稀疏的图上，这种复杂度的算法可能快得多参考书：T. H. Corman 等，Introduction to Algorithms，MIT Press（高等教育出版社影印，2001）MST 问题的研究还没有结束已确定时间复杂度下界为 O(|E|)，但还没有找到这样的算法显然，如果 |E| |V|-1 时没有最小生成树，很容易判断9/2/202444问题与讨论9/2/202445