《数据结构MapleRelated.ppt》由会员分享，可在线阅读，更多相关《数据结构MapleRelated.ppt（45页珍藏版）》请在三一文库上搜索。
1、数据结构 -Maple Related- 牟克典 数学科学学院信息科学系 2012秋季 11/20/20121 第五讲 图和图算法(1) 图：基本概念和性质 图的基本操作 图的遍历 宽度优先 深度优先 图的表示 生成树 最小生成树 2012年11月21日 10:10-12:00 三教303 11/20/20122 图（graph） 图是一种数学结构，数学里有分支 “图论”，研究一种拓扑结构 这里把它看着一类复杂数据结构，用于表示具有各种复杂关系的数据集 合。图在实际中应用很广泛 本章介绍图的最基本知识，图的基本实现方法，以及图的若干最基本的 计算问题和重要算法 重点算法（这些算法是本章最重要的
2、内容）： 图的深度优先搜索与广度优先搜索 最小生成树的 Prim 算法和 Kruskal 算法 求单源最短路径的 Dijkstra 算法 求所有顶点对之间最短路径的 Floyd 算法 拓扑排序 关键路径 11/20/20123 图：基本概念 图是二元组 G = ( V, E )，其中 V 是顶点的非空有穷集合（可有空图的概念，用处不大） E 是顶点偶对 (称为“边”) 的集合，E VV V 中的顶点也称为图 G 的顶点，E 中的边也称为图 G 的边 有向图：有向图中的边有方向，边是顶点的有序对 有序对用尖括号表示。 表示从 vi 到 vj 的有向边，vi 称为 边的始点，vj 是边的终点。 和
3、 表示两条不同 有向边 无向图：无向图中的边没有方向，是顶点的无序对 无序对用圆括号表示，(vi , vj) 和 (vj , vi) 表示同一条无向边 如果图 G 里有边 E 或者 (vi, vj) E 顶点 vj 称为 vi 的邻接顶点（对无向图，邻接点是双向的） 这种边称为与顶点 vi 相关联的边或 vi 的邻接边 与有序树类似，图中的邻接边也可以规定顺序 11/20/20124 图 图可用图形自然表示（圆圈表示顶点，线段或箭头表示边） v1 v2 v3 G1 v1 v4 v3 v3 G2 v1 v2v3 v7v6v5v4 G3 两个限制：1）不考虑顶点到自身的边，若 (vi ,vj) 或
4、 是 G 的 边，则要求 vi vj；2）顶点间没有重复出现的边，若 (vi ,vj) 或 是 G 的边，则它是这两个顶点间的唯一边（不存在多重边） 去掉这些限制得到稍微不同的数学研究对象。图论中也研究它们 11/20/20125 图：概念和性质 完全图：任意两个顶点之间都有边的图（有向图或无向图）。显然： n 个顶点的无向完全图有 n*(n-1)/2 条边 n 个顶点的有向完全图有 n*(n-1) 条边 注意图上的重要事实：|E| |V|2，或者 |E| O( |V|2 ) 度（顶点的度）：与一个顶点关联的边的个数。 对于有向图，还分为出度和入度，分别表示以该顶点为始点或者终点 的边的个数
5、无论是有向图还是无向图，顶点数 n，边数 e 和度数满足下面关系: 其中 D(vi) 表示 vi 的度数 11/20/20126 路径和相关概念 路径：对图 G = (V, E)，若存在顶点序列 vi0,vi1,vi(m)，使 (vi0,vi1)，(vi1,vi2), (vi(m-1), vi(m) 都在 E 中（对有向图 , , , 都在 E 中) 则说从顶点vi0到vi(m) 存在一条路径 称为从 vi0 到 vi(m) 的路径 路径长度：路径上边的条数 回路（环）：起点和终点相同的路径 如果除起点和终点外的其他顶点均不相同，则称为简单回路 简单路径：内部不包含环路的路径， 即，路径上的顶
6、点除起点和终点可能相同外，其它顶点均不相同 简单回路也是简单路径 11/20/20127 子图、有根图 对图 G = (V，E) 和 G = (V，E)，如果 V V 且 E E ，就称 G 是 G 的子图。特别的，G 是其自身的子图 下面是有向图G1的几个子图 G1 v1v 1 v1 v 2 v 2 v2 v2 v3 v1 v 2 v 3 有根图 q 如果有向图 G 中存在一个顶点 v，从 v 有路径可以到达图 G 中其 它所有顶点，则称 G 为一个有根图，v 称为图 G 的一个根 q 有根图中的根可能不唯一 11/20/20128 连通图 连通：如果无向图 G 中存在从 vi 到 vj 的
7、路径（显然它也是从 vj到 vi 的路 径)，则称 vi 与 vj 连通（默认顶点 v 到自身连通） 无向图的连通性 连通图：如果无向图 G 中的任意两个不同顶点 vi 和 vj 之间都连通（都存在路径 ），则称 G 为连通图 极大连通子图是图中极大的连通子图（没有真包含它连通子图） 连通分量：无向图 G 的一个极大连通子图称为 G 的一个连通分量。若 G 不连通 ，其连通分量将多于一个，它们形成 G 的一个划分 有向图的连通性 强连通图：如果有向图 G 中任意两个不同顶点 vi 和 vj 之间都存在从 vi 到 vj 以 及从 vj 和 vi 的路径，则称 G 是一个强连通图 强连通分量：有
8、向图G的极大强连通子图称为它的强连通分量 有向图 G 的强连通分量形成其顶点的一个划分 11/20/20129 带权图和网络 若图 G 的每条边都被赋以一个权值，G 称为是带权图 权值可用于表示实际应用中与顶点关联有关的某种量 带权的连通无向图称为网络 下图为一个网络 网络是实际应用非常广泛的一类图结构 后面会介绍网络上的一些重要性质和算法、以及它们的应用 11/20/201210 图的基本操作 作为复杂的数据结构，图上可能定义许多操作。下面列举一些操作 创建空图，判断图 g 是否空图，把图 g 置为空图： createGraph ( ) isEmptyGraph ( g ) clearGra
9、ph ( g ) 图中顶点个数（order）和边个数（size） order( g ) size( g ) 图中所有顶点的集合，所有边的集合： vertices ( g )edges( g ) 图 g 中顶点 v 的入度和出度（结果用二元序列表示）： vdeg ( g , v ) 在图 g 中增加一条边 或 (v1,v2)： addEdge ( g , v1 , v2 ) 11/20/201211 图的基本操作 检查图 g 中是否存在边 或 (v1,v2)： findEdge ( g , v1 , v2 ) 在图 g 中删除边 或 (v1,v2)： deleteEdge ( g , v1 ,
10、v2 ) 找出图 g 中与顶点 v 相邻的顶点（集合或表）： adjacentVertices ( g , v ) 在图 g 中删除一顶点和与之关联的所有边： deleteVertex ( g , v ) 图中的遍历操作。与树遍历的关键差异包括： 要防止走到已遍历过的部分 要考虑图的连通性问题（图可能不连通，遍历完一个连通分支后还不能 结束，需要去遍历其他分支） 11/20/201212 图的遍历 图的遍历 按某种方式系统访问图中所有顶点，且每个顶点仅访问一次的过程 也称为图的周游 遍历的基本部分是访问一个顶点所在的连通分支（对有向图，强 连通分支）的全部顶点。如果不是连通图，还需要访问其他连
11、通 分支 基本的图遍历方法同样是： 深度优先遍历（通过深度优先搜索的方式遍历） 广度优先遍历（通过广度优先搜索的方式遍历） 两种方式对有向图和无向图都适用 11/20/201213 深度优先遍历 深度优先遍历 (Depth-First Traversal) 的策略就是按照深度优先搜索（ Depth-First Search）的方式遍历，做法是： 从指定顶点 v 出发，先访问 v 并将其标记为已访问 依次从 v 的未访问过的各邻接顶点 w 出发进行深度优先搜索（要取得 v 的邻接 顶点，可能排列一种顺序），直到图中与 v 连通的所有顶点都访问过（递归） 如果图中还有未访问顶点，则选一个未访问顶点
12、，由它出发重复上述过程，直到 图中所有顶点都已访问为止 对图进行深度优先遍历，按访问顶点的先后次序得到的顶点序列，称为该 图的深度优先搜索序列（ Depth-First Search 序列），通常简称为 DFS 序列 由于遍历中邻接点通常有多个，对它们的不同（递归）访问顺序将得到不同的 DFS 序列（不唯一） 如果规定了图中个顶点的邻接点顺序，DFS 序列就确定了 11/20/201214 深度优先遍历 一个简单示例： V7V6 V3 V2 V5 V1 V8 V4 假定各顶点的邻接顶点从左到右排序，得到的 DFS 序列： 11/20/201215 深度优先遍历算法 这个示意算法说明了 DFS
13、的过程，基本部分是遍历一个连 通分支 DFTGraph := proc(g:Graph) while existUnvisited(g) do DFSComponent(g, nextUnvisited(g) od end: 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 od end: 11/20/201216 广
14、度优先遍历 广度优先遍历 (Breadth-First Traversal) 的遍历方式是通过广度优先搜索 （Breadth-First Search），具体过程是： 从指定顶点 v 出发，先访问顶点 v 并将其标记为已访问 依次访问 v 的所有相邻顶点 v1, v2, , vm （可以为 v 的邻接顶点假定一种顺 序） ，然后依次访问与 v1, v2, , vm 邻接的所有未访问顶点（递归） 直到所有已访问顶点的相邻顶点都已访问为止 如果图中还有未访问顶点，则选择一个未访问顶点，由它出发进行广度优先搜索 ，直到所有顶点都已访问为止 通过广度优先遍历得到的顶点序列称为图中顶点的广度优先搜索序列
15、（ Breadth-First Search 序列）或BFS序列 由于遍历中邻接点通常有多个，对它们的不同（递归）访问顺序将得到不同的 BFS 序列（不唯一） 如果规定了图中各顶点的邻接点顺序，BFS 序列就确定了 11/20/201217 广度优先遍历 简单示例： V7V6 V3 V2 V5 V1 V8 V4 假定各顶点的邻接顶点从左到右排序，得到的 BFS 序列： 11/20/201218 广度优先遍历 BFTGraph := proc(g:Graph) while existUnvisited(g) do BFSComponent(g, nextUnvisited(g) od end:
16、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 od end: 11/20/201219 图的表示 图的结构比较复杂，任意两个顶点间都可能存在边 需要表示顶点及顶点间的边
17、，存储方法很多 应根据具体应用和需要做的操作，选择图的存储表示法 图的最基本表示方法是邻接矩阵表示法 表示图的邻接矩阵通常非常稀疏。很多图中边的个数与顶点个数成线 性关系，如中国铁路线路图 人们提出了其他表示方法，都可看着邻接矩阵的“压缩”版本 直接邻接矩阵存储空间可能浪费较大，人们考虑了各种变形，如： 邻接表表示法 邻接多重表表示法 图的十字链表，等 下面只介绍邻接表表示法 11/20/201220 图的表示：邻接矩阵 邻接矩阵是一个矩阵，其中表示了图中顶点间的邻接关系 设 G = (V，E) 为 n 个顶点的图，其邻接矩阵为如下 n 阶方阵 ： 的权，图 G 的邻接矩阵定义为（用邻 接矩阵
18、元素记录边的权）： = 或若 或 或若 vvvv vvvvw jiA jiji jijiij ,),( 0 ,),( , 不是图G的边 是图G的边 下面带权图的两个邻接矩阵分别为A3和A4，根据需要用 0 或表示无边 = 0100110 100248 02065 114603 08530 3 A = 1011 10248 265 11463 853 4 A 11/20/201223 在 Maple 里实现邻接矩阵 在 Maple 里用邻接矩阵方法实现图，内部表示可以用两个成分 ： 一个 n 元素的一维 Array 存储顶点信息 一个 nn 的二维 Array 表示邻接矩阵 这种表示需要首先确定
19、图中顶点个数。可以加入/删除边，但顶点的 情况固定了 采用这种实现，操作和空间利用效率高，但灵活性稍差 另一种可能设计是利用 Maple 的 table 用两个 table 分别存储邻接矩阵和顶点信息 给每个顶点一个标识（整数或者唯一名字），用这种标识建立两部分 信息之间的联系 这种表示可以支持任意的顶点/边加入和删除 这种表示实际是利用 Maple 的 table 机制（散列表，后面介绍）的 灵活性，操作效率通常也比较高，但可能占用的空间大些 11/20/201224 邻接表表示法 邻接表表示的形式与树的“子表表示”相同，用 一个顶点表表示图中顶点信息 每个顶点关联一个邻接表，记录与之相关的
20、邻接顶点 无向图： 一个顶点表，每个顶点有一个关联边的表 边 (vi,vj) 在顶点 vi，vj 的边表各有一结点，在边表中存储两次 顶点 vi 的边表中结点个数为顶点 vi 的度 v1 v2 v3 v4 2 1 1 1 3 3 2 2 4 4 1 2 3 4 11/20/201225 邻接表表示法 有向图有向图 一个顶点表，每个顶点关联一个边表 顶点 vi 的边表中每个结点对应的是以 vi 为始点的一条边，因此 ，将有向图邻接表的边表称为出边表 顶点 vi 的边表中结点个数为顶点 vi 的出度 也可采用入边的表，表中结点个数是顶点的入度 v1 v2 v3 v4 4 1 1 3 4 1 2 3
21、 4 v1v4 v2v3 出边表 11/20/201226 邻接表表示法 v1 v2 v3 v4 2 1 2 1 5 v1 v2 v3 v5 2 1 3 4 3 5 2 v4 v5 4 4 存储出边表的情况存储入边表的情况 11/20/201227 生成树 生成树的概念 从连通无向图或强连通有向图 G 中的任一顶点 v0 出发，或从有根有向 图的根 v0 出发，存在到图中其他各结点的路径 若 G 有 n 个顶点，必然可找到 n-1 条边，其中包含了从 v0 到其他所有 结点的路径（很容易通过数学归纳法证明）。这样的 n-1 条边形成 G 的 一个子图 T（包含 G 所有顶点和 n-1 条边）
22、对无向图 G，这样的子图 T 是一个最小连通子图（去掉任意一条边后不 再连通）。n 个顶点 n-1 条边的图成树形，因此称子图 T 为 G 的生成 树。对有向图的定义类似。图的生成树可能不唯一 性质：n 个顶点的连通图的生成树包含恰好 n-1 条边 无向“树”就是连通的无环图。有向“树”的边都位于从根到其他结点 的（有方向的）路径上 非连通的无向图可划分为一组连通分量，可以定义它们的生成树林 n 个顶点 m 个连通分量的图 G 的生成森林恰好包含 n-m 条边 11/20/201228 遍历和生成树 从连通无向图或强连通有向图中任一顶点出发遍历，或从有根有向图的 根顶点出发遍历，都可以访问到所
23、有顶点 遍历经过的边加上所有顶点，就构成该图的一棵生成树 构造生成树的过程可以按深度优先遍历或广度优先遍历 遍历中记录访问的所有顶点和经过的边，就得到深度优先生成树，或广度优先 生成树，简称为 DFS 生成树或 BFS 生成树 无向图 DFS生成树BFS生成树 11/20/201229 遍历生成树 也可把连通无向图的生成树定义为包含其全部顶点的最小连通子图，一般无向图 的生成树林定义为各连通分量的最小连通子图的集合 也可以把强连通有向图的生成树定义为包含了其全部顶点的最小有根子图（有向 树，去掉一条边就不是有根图了） 生成树描述了图的一种框架结构，也称为支撑树 有向图的遍历产生的生成树 11/
24、20/201230 最小生成树 网络 G（带权连通无向图）的边带有权值，其生成树中各条边的权值之 和称为该生成树的权 网络 G 可能有多棵不同生成树，其权值可能不同。其中权值最小的生 成树称为 G 的最小生成树 (Minimum Spanning Tree，MST) 最小生成树可能不唯一 最小生成树有许多实际应用： 把网络顶点看作城市，边的权看作连接城市的通讯线路成本。根据最小 生成树建立的是城市间成本最低的通讯网 可类似考虑成本最低的公路网等 农村村庄之间的输电网络、有线电视网 输水管线、暖气管线、配送中心与线路的规划 集成电路或印刷电路版的地线，供电线路 等等 11/20/201231 最
25、小生成树：MST 性质 MST 性质： 设 G = (V，E) 是网络，U 是V 的任 一真子集，e = (u,v) E，其中 uU ，vV - U，而且 在 G 中所有一端 点在 U 另一端点在 V - U 的边中e的 权值最小 G 必有一棵包括边 e 的最小生成树（ 网络总有最小生成树） MST 性质的证明： 任取 G 的一棵最小生成树T，T 中必 有一条一端在 U 另一端在 V-U 的边 ，设为 e。T 加上 e 得到一个包含环 路的图，去掉 e 得到另一生成树，其 权值不大于 T，因此是最小生成树 U V - U 图 G ee 11/20/201232 最小生成树：Prim 算法 基本
26、思想是从一个顶点出发，直接利用 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 的一棵
27、最小生成树 这个算法直接利用 MST 性质构造最小生成树 算法的正确性：这一算法最后得到的必然是 G 的最小生成树 请考虑如何证明这个算法的正确性 11/20/201233 Prim 算法示例 11/20/201234 Prim 算法实现的思想 已知图 G 图采用邻接矩阵表示，构造该图的最小生成树 使用的数据表示： 用顶点对的下标 (在顶点表中的下标) 表示边。例如： 1, 2, 10 表示顶点 1 到顶点 2 的边上的权为 10 用一个 n-1 元的数组 mst（n为顶点数），其中保存一组边 算法开始时设想 v1 在最小生成树的顶点集 U 里，mst 里记录从 v1 到 其余顶点的最短边（都
28、是最短边）和权（无边时权值看作无穷） 算法执行中反复选择当时 mst 里与 U 中顶点之间的边中权值最小的另 一顶点加入 U，同时更新 mst 里记录的到其他顶点的边和权，使 mst 始终记录从 U 到其他顶点的最短边和权 具体方法是让 mst 前段记录已知属于最小生成树的边，后面记录 U 到不 属于 U 的顶点的最小权的边 算法结束时 mst 中存放着最小生成树的n-1条边 11/20/201235 Prim 算法实现梗概 算法实现梗概： 开始时只有 v1 属于最小生成树 T 的结点集 U，将 mst 初始化为从 v1 到其他各顶点的边和权值，无边时权值取无穷大。在 Maple 里无 穷大用
29、 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 里剩下的边权都是无穷大，那么图不连通，无最小生成树 11/20/201236 Pr
30、im 算法运行情况 例：已知下面图 G 及其邻接矩阵，构造该图的最小生成树 033141121 3301819 1418066 605 1165010 2119100 1、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) 加入最小生成树。 而后考虑是否要替换一些点的“已知最近路径” 11/20/201237 Prim 算法运行情况 033141121 3301819 1418066 605 1165
31、010 2119100 3、考虑 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)加入最小生成树 11/20/201238 Prim 算法运行情况 5、考虑 mst3 到
32、 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) 加入最小生成树 033141121 3301819 1418066 605 1165010 2119100 11/20/201239 Prim 算法运行情况 033141121 3301819 1418066 605 11
33、65010 2119100 7、考虑 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 11/20/201240 Prim 算法运行情况 033141121 3301819
34、1418066 605 1165010 2119100 9、考虑调整 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 11/20/201241 Prim 算法的 Maple 描述 prim := proc(vmun, adjMat) local i, j, weight, mn, tmp, vx, vy, mst; mst := Array(1vnum-1); for
35、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
36、to vnum-1 do #检查是否需要替换边 vy := mstj2; weight := adjMatvx,vy; if evalb(weight mstj3) then mstj := vx, vy, weight fi od od end: 11/20/201242 Prim 算法的复杂性分析 Prim算法的时间主要用在选择最小生成树的 n-1 条边和选择后检查 和替换边时。外循环执行 n-1 次，包含两个内循环，时间耗费为： 算法的时间复杂度是 O(|V|2) 算法的空间复杂度：算法中主要就是用了一个数组 mst 该数组的大小正比与顶点个数 由此算法的空间复杂度是 O(|V|) 应该
37、觉得这一算法有可能改进。关键操作（也是提高效率的关键） q 找出分界边中最短的边 q 检查是否需要更新分界边 11/20/201243 Prim 算法的复杂性分析 采用不同辅助数据结构，可使 Prim算法的复杂度变为 O(|E| log |V|)，其中 |E| 和 |V| 是边集合和结点集合 的大小。在边比较稀疏的图上，这种复杂度的算法可能快 得多 参考书：T. H. Corman 等，Introduction to Algorithms，MIT Press（高等教育出版社影印，2001） MST 问题的研究还没有结束 已确定时间复杂度下界为 O(|E|)，但还没有找到这样的算法 显然，如果 |E| |V|-1 时没有最小生成树，很容易判断 11/20/201244 问题与讨论 11/20/201245