《六章节图.ppt》由会员分享，可在线阅读，更多相关《六章节图.ppt（99页珍藏版）》请在三一文库上搜索。
1、第六章 图,任课教员：张 铭 http:/ 北京大学信息科学与技术学院 网络与信息系统研究所 版权所有，转载或翻印必究,北京大学信息学院 版权所有，转载或翻印必究 Page 2,主要内容,6.1 图的基本概念 6.2 图的抽象数据类型 6.3 图的存储结构 6.4 图的周游（深度、广度、拓扑） 6.5 最短路径问题 6.6 最小支撑树,北京大学信息学院 版权所有，转载或翻印必究 Page 3,6.1 图的基本概念,习惯上，常用G=（V，E）代表一个图 。 顶点（vertex） 边（edge） 边的始点 边的终点 稀疏图（sparse graph） 密集图（dense graph） 完全图（c
2、omplete graph）,北京大学信息学院 版权所有，转载或翻印必究 Page 4,6.1 图的基本概念（续）,无向图（undirected graph） 图中代表一条边的顶点的偶对无方向性，也即无序 有向图（directed graph或digraph） 图中代表一条边的顶点的偶对是有序的,北京大学信息学院 版权所有，转载或翻印必究 Page 5,6.1 图的基本概念（续）,无向图示例,有向图示例,北京大学信息学院 版权所有，转载或翻印必究 Page 6,6.1 图的基本概念（续）,标号图（labeled graph） 带权图（weighted graph）,北京大学信息学院 版权所有，
3、转载或翻印必究 Page 7,6.1 图的基本概念（续）,顶点的度（degree） 与该顶点相关联的边的数目。 入度(in degree) 出度(out degree) 子图（subgraph） 图G=(V，E)，G=(V，E)中，若VV，EE，并且E中的边所关联的顶点都在V中，则称图G是图G的子图,北京大学信息学院 版权所有，转载或翻印必究 Page 8,6.1 图的基本概念（续）,路径（path） 在图G=(V，E)中，如果存在顶点序列Vp，Vi1，Vi2，Vin，Vq，使得（Vp，Vi1），(Vi1，Vi2) ，(Vin，Vq)（若对有向图，则使得， ，）都在E中，则称从顶点Vp到顶点V
4、q存在一条路径。 简单路径（simple path） 路径长度（length）,北京大学信息学院 版权所有，转载或翻印必究 Page 9,6.1 图的基本概念（续）,回路（cycle，也称为环） 简单回路（simple cycle） 无环图（acyclic graph） 有向无环图（directed acyclic graph，简写为DAG）,北京大学信息学院 版权所有，转载或翻印必究 Page 10,6.1 图的基本概念（续）,有根的图 一个有向图中，若存在一个顶点V0，从此顶点有路径可以到达图中其它所有顶点，则称此有向图为有根的图，V0称作图的根。 连通的（connected） 对无向图G
5、=（V，E）而言，如果从V1到V2有一条路径（从V2到V1也一定有一条路径），则称V1和V2是连通的（connected） 。 强连通,北京大学信息学院 版权所有，转载或翻印必究 Page 11,6.1 图的基本概念（续）,连通分支或者连通分量（connected component） 无向图的最大连通子图。 强连通分支（强连通分量）。 网络 带权的连通图。 自由树（free tree） 不带有简单回路的无向图，它是连通的，并且具有|V|-1条边。,北京大学信息学院 版权所有，转载或翻印必究 Page 12,6.2 图的抽象数据类型,class Graph /图的ADT public: int
6、 VerticesNum(); /返回图的顶点个数 int EdgesNum(); /返回图的边数 /返回与顶点oneVertex相关联的第一条边 Edge FirstEdge(int oneVertex); /返回与边PreEdge有相同关联顶点oneVertex的 /下一条边 Edge NextEdge(Edge preEdge);,北京大学信息学院 版权所有，转载或翻印必究 Page 13,6.2 图的抽象数据类型（续）,/添加一条边 bool setEdge(int fromVertex,int toVertex,int weight); /删一条边 bool delEdge(int
7、fromVertex,int toVertex); /如果oneEdge是边则返回TRUE，否则返回FALSE bool IsEdge(Edge oneEdge);,北京大学信息学院 版权所有，转载或翻印必究 Page 14,6.2 图的抽象数据类型（续）,/返回边oneEdge的始点 int FromVertex(Edge oneEdge); /返回边oneEdge的终点 int ToVertex(Edge oneEdge); /返回边oneEdge的权 int Weight(Edge oneEdge); ;,北京大学信息学院 版权所有，转载或翻印必究 Page 15,6.3 图的存储结构,
8、6.3.1 图的相邻矩阵（adjacency matrix）表示法 6.3.2 图的邻接表（adjacency list）表示法 邻接多重表(adjacency multilist)表示法,北京大学信息学院 版权所有，转载或翻印必究 Page 16,6.3.1 图的相邻矩阵（adjacency matrix）表示法,相邻矩阵 表示顶点间相邻关系的矩阵。 若G是一个具有n个顶点的图，则G的相邻矩阵是如下定义的nn矩阵： Ai,j=1，若（Vi，Vj）（或）是图G的边； Ai,j=0，若（Vi，Vj）（或）不是图G的边。 相邻矩阵的空间代价为O(n2),北京大学信息学院 版权所有，转载或翻印必究
9、Page 17,6.3.1 图的相邻矩阵（adjacency matrix）表示法（续）,A7=,北京大学信息学院 版权所有，转载或翻印必究 Page 18,6.3.1 图的相邻矩阵（adjacency matrix）表示法（续）,A4=,北京大学信息学院 版权所有，转载或翻印必究 Page 19,6.3.2 图的邻接表（adjacency list）表示法,北京大学信息学院 版权所有，转载或翻印必究 Page 20,6.3.2 图的邻接表（adjacency list）表示法（续）,G6邻接表表示,北京大学信息学院 版权所有，转载或翻印必究 Page 21,6.3.2 图的邻接表（adjac
10、ency list）表示法（续）,G7的出边表,G7的入边表,北京大学信息学院 版权所有，转载或翻印必究 Page 22,邻接多重表(adjacency multilist),把邻接表表示中代表同一条边的两个表目合为一个表目 图的每条边只用一个多重表表目表示 包括此边的两个顶点的序号 两个指针（一个指针指向与第一个顶点相关联的下一条边，另一个指针指向与第二个顶点相关联的下一条边） 在以处理图的边为主，要求每条边处理一次的实际应用中特别有用。,北京大学信息学院 版权所有，转载或翻印必究 Page 23,邻接多重表(adjacency multilist),G6的邻接多重表表示,北京大学信息学院
11、版权所有，转载或翻印必究 Page 24,有向图邻接多重表(adjacency multilist),在顶点表中设计两个指针 第一个指向以此顶点为始点的第一条边 第二个指向以此顶点为终点的第一条边 边表 第一个指针指向始点与本边始点相同的下一条边 第二个指针指向终点与本边终点相同的下一条边 故仅用表中第一个链便得到有向图的出边表，仅用第二个链便得到有向图的入边表,北京大学信息学院 版权所有，转载或翻印必究 Page 25,邻接多重表(adjacency multilist) （续）,G7的邻接多重表表示,北京大学信息学院 版权所有，转载或翻印必究 Page 26,6.3.2 图的邻接表（adj
12、acency list）表示法（续）,n个顶点m条边的无向图 需用(n+2m)个存储单元 n个顶点m条边的有向图 需用(n+m)个存储单元,北京大学信息学院 版权所有，转载或翻印必究 Page 27,6.4 图的周游,图的周游（graph traversal） 给出一个图G和其中任意一个顶点V0，从V0出发系统地访问G中所有的顶点，每个顶点访问一次，这叫做图的周游。,北京大学信息学院 版权所有，转载或翻印必究 Page 28,6.4 图的周游（续）,图的周游的典型算法 从一个顶点出发，试探性访问其余顶点，同时必须考虑到下列情况： 从一顶点出发，可能不能到达所有其它的顶点，如非连通图； 也有可能
13、会陷入死循环，如存在回路的图。 解决办法 为图的每个顶点保留一个标志位（mark bit）； 算法开始时，所有顶点的标志位置零； 在周游的过程中，当某个顶点被访问时，其标志位就被标记为已访问。,北京大学信息学院 版权所有，转载或翻印必究 Page 29,6.4 图的周游（续）,/图的周游算法的实现 void graph_traverse(Graph ,北京大学信息学院 版权所有，转载或翻印必究 Page 30,6.4 图的周游（续）,图的生成树 图的所有顶点加上周游过程中经过的边所构成的子图称作图的生成树。 图的生成森林。,北京大学信息学院 版权所有，转载或翻印必究 Page 31,6.4.1
14、 深度优先搜索,深度优先搜索（depth-first search，简称DFS）基本思想 访问一个顶点V，然后访问该顶点邻接到的未被访问过的顶点V， 再从V出发递归地按照深度优先的方式周游， 当遇到一个所有邻接于它的顶点都被访问过了的顶点U时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点W， 再从W出发递归地按照深度优先的方式周游， 最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则周游结束。 深度优先搜索树（depth-first search tree）,北京大学信息学院 版权所有，转载或翻印必究 Page 32,6.4.1 深度优先搜索（续）,深度优先搜索的顺序是a
15、，b，c，f，d，e，g,北京大学信息学院 版权所有，转载或翻印必究 Page 33,6.4.1 深度优先搜索（续）,void DFS(Graph /访问V ,北京大学信息学院 版权所有，转载或翻印必究 Page 34,6.4.1 深度优先搜索（续）,深度优先搜索算法的时间复杂度 DFS对每一条边处理一次（无向图的每条边从两个方向处理），每个顶点访问一次。 采用邻接表表示时，有向图总代价为(|V|+|E|)，无向图为(|V|+2|E|) 采用相邻矩阵表示时，处理所有的边需要(|V|2)的时间 ，所以总代价为(|V|+|V|2)= (|V|2)。,北京大学信息学院 版权所有，转载或翻印必究 Pa
16、ge 35,6.4.2 广度优先搜索,广度优先搜索（breadth-first search，简称BFS） 它的基本思想是访问顶点V0， 然后访问V0邻接到的所有未被访问过的顶点V01，V02，V0i， 再依次访问V01，V02，V0i邻接到的所有未被访问的顶点， 如此进行下去，直到访问遍所有的顶点。 广度优先搜索树（breadth-first search tree）,北京大学信息学院 版权所有，转载或翻印必究 Page 36,6.4.2 广度优先搜索（续）,广度优先搜索的顺序是a，b，d，e，f，c，g,北京大学信息学院 版权所有，转载或翻印必究 Page 37,6.4.2 广度优先搜索（
17、续）,/广度优先搜索算法的实现 void BFS(Graph while(!Q.empty() /如果队列仍然有元素,北京大学信息学院 版权所有，转载或翻印必究 Page 38,6.4.2 广度优先搜索（续）, int V=Q.front(); /顶部元素 Q.pop(); /出队 /将与该点相邻的每一个未访问点都入队 for(Edge e=G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e) if(G.MarkG.ToVertex(e)= UNVISITED),北京大学信息学院 版权所有，转载或翻印必究 Page 39,6.4.2 广度优先搜索（续）, G.
18、MarkG.ToVertex(e)=VISITED; Visit(G, G.ToVertex(e); /入队 Q.push(G.ToVertex(e); ,北京大学信息学院 版权所有，转载或翻印必究 Page 40,6.4.2 广度优先搜索（续）,广度优先搜索算法的时间复杂度 与深度优先搜索算法的时间复杂度相同,北京大学信息学院 版权所有，转载或翻印必究 Page 41,6.4.3 拓扑排序,先决条件问题。 拓扑排序（topological sort） 将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序,北京大学信息学院 版权所有，转载或翻印必究 Page 4
19、2,6.4.3 拓扑排序（续）,拓扑序列 对于有向无环图G=（V，E），V里顶点的线性序列称作一个拓扑序列，如果该顶点序列满足： 若在有向无环图G中从顶点Vi到Vj有一条路径，则在序列中顶点Vi必在顶点Vj之前。,北京大学信息学院 版权所有，转载或翻印必究 Page 43,6.4.3 拓扑排序（续）,课程代号 课程名称 先修课程 C1 高等数学 C2 程序设计 C3 离散数学 C1，C2 C4 数据结构 C2，C3 C5 算法语言 C2 C6 编译技术 C4，C5 C7 操作系统 C4，C9 C8 普通物理 C1 C9 计算机原理 C8,北京大学信息学院 版权所有，转载或翻印必究 Page 4
20、4,6.4.3 拓扑排序（续）,学生课程的安排图,北京大学信息学院 版权所有，转载或翻印必究 Page 45,6.4.3 拓扑排序（续）,任何无环有向图，其顶点都可以排在一个拓扑序列里，其拓扑排序的方法是： （1）从图中选择一个入度为0的顶点且输出之。 （2）从图中删掉此顶点及其所有的出边。 （3）回到第（1）步继续执行。,北京大学信息学院 版权所有，转载或翻印必究 Page 46,6.4.3 拓扑排序（续）,/队列方式实现的拓扑排序 void TopsortbyQueue(Graph /图中入度为0的顶点入队 while(!Q.empty() /如果队列中还有图的顶点,北京大学信息学院 版权
21、所有，转载或翻印必究 Page 47,6.4.3 拓扑排序（续）,int V=Q.front(); /顶部元素 Q.pop(); /一个顶点出队 Visit(G, V); /访问该顶点 G.MarkV=VISITED; /边e的终点的入度值减1 for(Edge e= G.FirstEdge(V); G.IsEdge(e);e=G.NextEdge(e) G.IndegreeG.ToVertex(e)-; if(G.IndegreeG.ToVertex(e)=0) Q.push(G.ToVertex(e); /入度为0的顶点入队 ,北京大学信息学院 版权所有，转载或翻印必究 Page 48,6
22、.4.3 拓扑排序（续）,for(i=0; iG.VerticesNum(); i+) if(G.Marki=UNVISITED) Print(“图有环”); /图有环 break; ,北京大学信息学院 版权所有，转载或翻印必究 Page 49,6.4.3 拓扑排序（续）,/深度优先搜索实现的拓扑排序 void Do_topsort(Graphe=G.NextEdge(e) /访问V邻接到的所有未被访问过的顶点 if(G.MarkG.ToVertex(e)= UNVISITED),北京大学信息学院 版权所有，转载或翻印必究 Page 50,6.4.3 拓扑排序（续）,/递归调用 Do_tops
23、ort(G, G.ToVertex(e),result,tag); resulttag+=V; ,北京大学信息学院 版权所有，转载或翻印必究 Page 51,6.4.3 拓扑排序（续）,/深度优先搜索方式实现的拓扑排序,结果是颠倒的 void TopsortbyDFS(Graph i+) if(G.Marki= UNVISITED),北京大学信息学院 版权所有，转载或翻印必究 Page 52,6.4.3 拓扑排序（续）,Do_topsort(G,i,result,tag); /调用递归函数 for(i=G.VerticesNum()-1;i=0;i-) /逆序输出 Visit(G, resul
24、ti); 注：深度优先搜索方式实现的拓扑排序无法判断图是否存在环。,北京大学信息学院 版权所有，转载或翻印必究 Page 53,6.4.3 拓扑排序（续）,拓扑排序的时间复杂度 图的每条边处理一次 图的每个顶点访问一次 所以，深度优先搜索方式实现的拓扑排序的时间复杂度同图的深度优先搜索方式周游。 队列方式的拓扑排序：在有环的情况下会提前退出，从而可能没处理完所有的边和顶点。,北京大学信息学院 版权所有，转载或翻印必究 Page 54,6.4.3 拓扑排序（续）,队列方式拓扑排序的时间复杂度 关键是，算法开始时找出所有入度为0的顶点（同时可知道其它顶点的入度） 当采用相邻矩阵时，算法开始时找所有
25、入度为0的顶点需要 (|V|2)的时间，加上处理边、顶点的时间，总代价为(|V|2+|E|+|V|)= (|V|2) 当采用邻接表时，因为在顶点表的每个顶点中可以有一个字段来存储入度，所以只需(|V|)的时间，加上处理边、顶点的时间，总代价为(2|V|+|E|),北京大学信息学院 版权所有，转载或翻印必究 Page 55,6.5 最短路径问题,6.5.1 单源最短路径（single-source shortest paths） 指的是对已知图G=（V，E），给定源顶点sV，找出s到图中其它各顶点的最短路径。 6.5.2 每对顶点间的最短路径（all-pairs shortest paths）
26、指的是对已知图G=（V，E），任意的顶点Vi，VjV，找出从Vi到Vj的最短路径。,北京大学信息学院 版权所有，转载或翻印必究 Page 56,6.5.1 单源最短路径,Dijkstra算法基本思想： 把图中所有顶点分成两组 第一组包括已确定最短路径的顶点 第二组包括尚未确定最短路径的顶点； 按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去 直至从s出发可以到达的所有顶点都包括进第一组中。,北京大学信息学院 版权所有，转载或翻印必究 Page 57,6.5.1 单源最短路径（续）,在这个过程中，总保持从s到第一组各顶点的最短路径长度都不大于从s到第二组的任何顶点的最短路径长度，而且，每
27、个顶点都对应一个距离值： 第一组的顶点对应的距离值就是从s到该顶点的最短路径长度 第二组的顶点对应的距离值是从s到该顶点的只包括第一组的顶点为中间顶点的最短路径长度,北京大学信息学院 版权所有，转载或翻印必究 Page 58,6.5.1 单源最短路径（续）,Dijkstra算法的具体做法： 一开始第一组只包括顶点s，第二组包括其它所有顶点； s对应的距离值为0，而第二组的顶点对应的距离值这样确定： 若图中有边或者（s，Vi），则Vi的距离值为此边所带的权，否则Vi的距离值为。 然后，每次从第二组的顶点中选一个其距离值为最小的顶点Vm加入到第一组中；,北京大学信息学院 版权所有，转载或翻印必究
28、Page 59,6.5.1 单源最短路径（续）,每往第一组加入一个顶点Vm，就要对第二组的各顶点的距离值进行一次修正： 若加进Vm做中间顶点，使从s到Vi的最短路径比不加Vm的为短，则需要修改Vi的距离值。 修改后再选距离值最小的顶点加入到第一组中，如此进行下去，直到图的所有顶点都包括在第一组中或者再也没有可加入到第一组的顶点存在。,北京大学信息学院 版权所有，转载或翻印必究 Page 60,6.5.1 单源最短路径（续）,求上图中顶点V1到其它各顶点的最短路径,北京大学信息学院 版权所有，转载或翻印必究 Page 61,6.5.1 单源最短路径（续）,用Dijkstra算法的处理过程，源顶点
29、为V1,北京大学信息学院 版权所有，转载或翻印必究 Page 62,6.5.1 单源最短路径（续）,/Dijkstra算法 void Dijkstra(Graph,北京大学信息学院 版权所有，转载或翻印必究 Page 63,6.5.1 单源最短路径（续）,for(i=0;iG.VerticesNum();i+) int v=minVertex(G,D); /找到距离s最小的顶点 if(Dv.length=INFINITY) break; G.Markv=VISITED; /把该点加入已访问组 Visit(G,v); /打印输出 /刷新D中的值，因为v的加入D的值需要改变， /只要刷新与v相邻的
30、点的值 for(Edge e=G.FirstEdge(v); G.IsEdge(e);e=G.NextEdge(e),北京大学信息学院 版权所有，转载或翻印必究 Page 64,6.5.1 单源最短路径（续）,if(DG.ToVertex(e).length(Dv.length +G.Weight(e) DG.ToVertex(e).length=Dv.length +G.Weight(e); DG.ToVertex(e).pre=v; ,北京大学信息学院 版权所有，转载或翻印必究 Page 65,6.5.1 单源最短路径（续）,其中的Dist类可以如下定义： Class Dist int l
31、ength; /与源s的距离 int pre; /前面的顶点 ; 而minVertex()函数可用最小堆（Minheap）等方式实现。,北京大学信息学院 版权所有，转载或翻印必究 Page 66,6.5.1 单源最短路径（续）,Dijstra算法时间代价分析 如果minVertex()函数不采用最小堆的方式，而是通过两两比较来扫描D数组 因为每次minVertex()扫描需要进行|V|次，而在更新D值处总共扫描|E|次 所以本方法的总时间代价为(|V|2 + |E|) = (|V|2)，因为|E|在O(|V|2)中,北京大学信息学院 版权所有，转载或翻印必究 Page 67,6.5.1 单源最
32、短路径（续）,如果minVertex()函数采用最小堆的方式， 每次改变Di.length，可以通过先删除再重新插入的方法来改变顶点i在堆中的位置， 或者仅为某个顶点添加一个新值(更小的)，作为堆中新元素(而不作删除旧值的操作，因为旧值被找到时，该顶点一定被标记为VISITED，从而被忽略)。 不作删除旧值的缺点是，在最差情况下，它将使堆中元素数目由(|V|)增加到(|E|)，此时总的时间代价为(|V|+|E|)log|E|)，因为处理每条边时都必须对堆进行一次重排。,北京大学信息学院 版权所有，转载或翻印必究 Page 68,6.5.2 每对顶点间的最短路径,Floyd算法 算法思想： 假设
33、用相邻矩阵adj表示图 Floyd算法递归地产生一个矩阵序列adj(0)，adj(1)， adj(k) ， adj(n) adj(k)i，j等于从顶点Vi到顶点Vj中间顶点序号不大于k的最短路径长度,北京大学信息学院 版权所有，转载或翻印必究 Page 69,6.5.2 每对顶点间的最短路径(续),假设已求得矩阵adj(k-1)，那么从顶点Vi到顶点Vj中间顶点的序号不大于k的最短路径有两种情况： 一种是中间不经过顶点Vk，那么就有adj(k)i，j=adj(k-1)i，j 另一种是中间经过顶点Vk，那么adj(k)i，j adj(k-1)i，j，且adj(k)i，j= adj(k-1)i，k
34、+ adj(k-1)k，j,北京大学信息学院 版权所有，转载或翻印必究 Page 70,6.5.2 每对顶点间的最短路径（续）,北京大学信息学院 版权所有，转载或翻印必究 Page 71,6.5.2 每对顶点间的最短路径(续),/Floyd算法 void Floyd(Graphj+),北京大学信息学院 版权所有，转载或翻印必究 Page 72,6.5.2 每对顶点间的最短路径（续）,if(i=j) Dij.length=0; Dij.pre=i; else Dij=INFINITY; Dij.pre=-1; for(v=0;vG.VerticesNum();v+) for(Edge e=G.F
35、irstEdge(v); G.IsEdge(e);e=G.NextEdge(e) DvG.ToVertex(e).length=G.Weight(e); DvG.ToVertex(e).pre=v; ,北京大学信息学院 版权所有，转载或翻印必究 Page 73,6.5.2 每对顶点间的最短路径（续）,/如果两个顶点间的最短路径经过顶点v，则有 /Dij.length(Div.length+Dvj.length for(v=0;v(Div.length +Dvj.length) Dij.length =Div.length +Dvj.length; Dij.pre=Dvj.pre; ,北京大学信
36、息学院 版权所有，转载或翻印必究 Page 74,6.5.2 每对顶点间的最短路径（续）,注：其中Dist类型与Dijkstra算法用到的Dist类型一致。,北京大学信息学院 版权所有，转载或翻印必究 Page 75,6.5.2 每对顶点间的最短路径（续）,因为Floyd算法的时间复杂度主要在于三重for循环，所以很明显，其复杂度是O(nnn),北京大学信息学院 版权所有，转载或翻印必究 Page 76,6.6 最小支撑树,最小支撑树（minimum-cost spanning tree，简称MST） 对于带权的连通无向图G，其最小支撑树是一个包括G的所有顶点和部分边的图，这部分的边满足下列条
37、件： （1）这部分的边能够保证图是连通的； （2）这部分的边，其权的总和最小。,北京大学信息学院 版权所有，转载或翻印必究 Page 77,6.6 最小支撑树（续）,(a),(a)的MST,(a)的MST,北京大学信息学院 版权所有，转载或翻印必究 Page 78,6.6.1 Prim算法,Prim算法的具体操作是： 从图中任意一个顶点开始，首先把这个顶点包括在MST里， 然后在那些其一个端点已在MST里，另一个端点还未在MST里的边中，找权最小的一条边，并把这条边和其不在MST里的那个端点包括进MST里。 如此进行下去，每次往MST里加一个顶点和一条权最小的边，直到把所有的顶点都包括进MST里。,北京大学信息学院 版权所有，转载或翻印必究 Page 79,6.6.1 Prim算法（续）,证明用Prim算法构造的生成树确实是MST。 首先证明这样一个结论： 设T(V*，E*)是连通无向图G=(V，E)的一棵正在构造的生成树，又E中有边e=(Vx，Vy)，其中VxV*，Vy不属于V*，且e的权W(e)是所有一个端点在V*里，另一端不在V*里的边的权中最小者，则一定存在G的一棵包括T的MST包括边e=( Vx，Vy)。,