六章节图.ppt
第六章 图,任课教员：张 铭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）完全图（complete graph）,北京大学信息学院 版权所有，转载或翻印必究 Page 4,6.1 图的基本概念（续）,无向图（undirected graph）图中代表一条边的顶点的偶对无方向性，也即无序 有向图（directed graph或digraph）图中代表一条边的顶点的偶对是有序的,北京大学信息学院 版权所有，转载或翻印必究 Page 5,6.1 图的基本概念（续）,无向图示例,有向图示例,北京大学信息学院 版权所有，转载或翻印必究 Page 6,6.1 图的基本概念（续）,标号图（labeled graph）带权图（weighted graph）,北京大学信息学院 版权所有，转载或翻印必究 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到顶点Vq存在一条路径。简单路径（simple path）路径长度（length）,北京大学信息学院 版权所有，转载或翻印必究 Page 9,6.1 图的基本概念（续）,回路（cycle，也称为环）简单回路（simple cycle）无环图（acyclic graph）有向无环图（directed acyclic graph，简写为DAG）,北京大学信息学院 版权所有，转载或翻印必究 Page 10,6.1 图的基本概念（续）,有根的图一个有向图中，若存在一个顶点V0，从此顶点有路径可以到达图中其它所有顶点，则称此有向图为有根的图，V0称作图的根。连通的（connected）对无向图G=（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/图的ADTpublic:int 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 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 图的存储结构,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),北京大学信息学院 版权所有，转载或翻印必究 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 图的邻接表（adjacency list）表示法（续）,G7的出边表,G7的入边表,北京大学信息学院 版权所有，转载或翻印必究 Page 22,邻接多重表(adjacency multilist),把邻接表表示中代表同一条边的两个表目合为一个表目图的每条边只用一个多重表表目表示包括此边的两个顶点的序号两个指针（一个指针指向与第一个顶点相关联的下一条边，另一个指针指向与第二个顶点相关联的下一条边）在以处理图的边为主，要求每条边处理一次的实际应用中特别有用。,北京大学信息学院 版权所有，转载或翻印必究 Page 23,邻接多重表(adjacency multilist),G6的邻接多重表表示,北京大学信息学院 版权所有，转载或翻印必究 Page 24,有向图邻接多重表(adjacency multilist),在顶点表中设计两个指针第一个指向以此顶点为始点的第一条边第二个指向以此顶点为终点的第一条边边表第一个指针指向始点与本边始点相同的下一条边第二个指针指向终点与本边终点相同的下一条边故仅用表中第一个链便得到有向图的出边表，仅用第二个链便得到有向图的入边表,北京大学信息学院 版权所有，转载或翻印必究 Page 25,邻接多重表(adjacency multilist)（续）,G7的邻接多重表表示,北京大学信息学院 版权所有，转载或翻印必究 Page 26,6.3.2 图的邻接表（adjacency list）表示法（续）,n个顶点m条边的无向图需用(n+2m)个存储单元n个顶点m条边的有向图需用(n+m)个存储单元,北京大学信息学院 版权所有，转载或翻印必究 Page 27,6.4 图的周游,图的周游（graph traversal）给出一个图G和其中任意一个顶点V0，从V0出发系统地访问G中所有的顶点，每个顶点访问一次，这叫做图的周游。,北京大学信息学院 版权所有，转载或翻印必究 Page 28,6.4 图的周游（续）,图的周游的典型算法从一个顶点出发，试探性访问其余顶点，同时必须考虑到下列情况：从一顶点出发，可能不能到达所有其它的顶点，如非连通图；也有可能会陷入死循环，如存在回路的图。解决办法为图的每个顶点保留一个标志位（mark bit）；算法开始时，所有顶点的标志位置零；在周游的过程中，当某个顶点被访问时，其标志位就被标记为已访问。,北京大学信息学院 版权所有，转载或翻印必究 Page 29,6.4 图的周游（续）,/图的周游算法的实现void graph_traverse(Graph,北京大学信息学院 版权所有，转载或翻印必究 Page 30,6.4 图的周游（续）,图的生成树图的所有顶点加上周游过程中经过的边所构成的子图称作图的生成树。图的生成森林。,北京大学信息学院 版权所有，转载或翻印必究 Page 31,6.4.1 深度优先搜索,深度优先搜索（depth-first search，简称DFS）基本思想访问一个顶点V，然后访问该顶点邻接到的未被访问过的顶点V，再从V出发递归地按照深度优先的方式周游，当遇到一个所有邻接于它的顶点都被访问过了的顶点U时，则回到已访问顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，再从W出发递归地按照深度优先的方式周游，最后，当任何已被访问过的顶点都没有未被访问的相邻顶点时，则周游结束。深度优先搜索树（depth-first search tree）,北京大学信息学院 版权所有，转载或翻印必究 Page 32,6.4.1 深度优先搜索（续）,深度优先搜索的顺序是a，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)。,北京大学信息学院 版权所有，转载或翻印必究 Page 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 广度优先搜索（续）,/广度优先搜索算法的实现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.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 42,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 44,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()/如果队列中还有图的顶点,北京大学信息学院 版权所有，转载或翻印必究 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.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_topsort(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,resulti);注：深度优先搜索方式实现的拓扑排序无法判断图是否存在环。,北京大学信息学院 版权所有，转载或翻印必究 Page 53,6.4.3 拓扑排序（续）,拓扑排序的时间复杂度图的每条边处理一次图的每个顶点访问一次 所以，深度优先搜索方式实现的拓扑排序的时间复杂度同图的深度优先搜索方式周游。队列方式的拓扑排序：在有环的情况下会提前退出，从而可能没处理完所有的边和顶点。,北京大学信息学院 版权所有，转载或翻印必究 Page 54,6.4.3 拓扑排序（续）,队列方式拓扑排序的时间复杂度关键是，算法开始时找出所有入度为0的顶点（同时可知道其它顶点的入度）当采用相邻矩阵时，算法开始时找所有入度为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）指的是对已知图G=（V，E），任意的顶点Vi，VjV，找出从Vi到Vj的最短路径。,北京大学信息学院 版权所有，转载或翻印必究 Page 56,6.5.1 单源最短路径,Dijkstra算法基本思想：把图中所有顶点分成两组第一组包括已确定最短路径的顶点第二组包括尚未确定最短路径的顶点；按最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去直至从s出发可以到达的所有顶点都包括进第一组中。,北京大学信息学院 版权所有，转载或翻印必究 Page 57,6.5.1 单源最短路径（续）,在这个过程中，总保持从s到第一组各顶点的最短路径长度都不大于从s到第二组的任何顶点的最短路径长度，而且，每个顶点都对应一个距离值：第一组的顶点对应的距离值就是从s到该顶点的最短路径长度第二组的顶点对应的距离值是从s到该顶点的只包括第一组的顶点为中间顶点的最短路径长度,北京大学信息学院 版权所有，转载或翻印必究 Page 58,6.5.1 单源最短路径（续）,Dijkstra算法的具体做法：一开始第一组只包括顶点s，第二组包括其它所有顶点；s对应的距离值为0，而第二组的顶点对应的距离值这样确定：若图中有边或者（s，Vi），则Vi的距离值为此边所带的权，否则Vi的距离值为。然后，每次从第二组的顶点中选一个其距离值为最小的顶点Vm加入到第一组中；,北京大学信息学院 版权所有，转载或翻印必究 Page 59,6.5.1 单源最短路径（续）,每往第一组加入一个顶点Vm，就要对第二组的各顶点的距离值进行一次修正：若加进Vm做中间顶点，使从s到Vi的最短路径比不加Vm的为短，则需要修改Vi的距离值。修改后再选距离值最小的顶点加入到第一组中，如此进行下去，直到图的所有顶点都包括在第一组中或者再也没有可加入到第一组的顶点存在。,北京大学信息学院 版权所有，转载或翻印必究 Page 60,6.5.1 单源最短路径（续）,求上图中顶点V1到其它各顶点的最短路径,北京大学信息学院 版权所有，转载或翻印必究 Page 61,6.5.1 单源最短路径（续）,用Dijkstra算法的处理过程，源顶点为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相邻的点的值 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 Distint length;/与源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 单源最短路径（续）,如果minVertex()函数采用最小堆的方式，每次改变Di.length，可以通过先删除再重新插入的方法来改变顶点i在堆中的位置，或者仅为某个顶点添加一个新值(更小的)，作为堆中新元素(而不作删除旧值的操作，因为旧值被找到时，该顶点一定被标记为VISITED，从而被忽略)。不作删除旧值的缺点是，在最差情况下，它将使堆中元素数目由(|V|)增加到(|E|)，此时总的时间代价为(|V|+|E|)log|E|)，因为处理每条边时都必须对堆进行一次重排。,北京大学信息学院 版权所有，转载或翻印必究 Page 68,6.5.2 每对顶点间的最短路径,Floyd算法 算法思想：假设用相邻矩阵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+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.FirstEdge(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.lengthfor(v=0;v(Div.length+Dvj.length)Dij.length=Div.length+Dvj.length;Dij.pre=Dvj.pre;,北京大学信息学院 版权所有，转载或翻印必究 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的所有顶点和部分边的图，这部分的边满足下列条件：（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)。,北京大学信息学院 版权所有，转载或翻印必究 Page 80,6.6.1 Prim算法（续）,用反证法设G的任何一棵包括T的MST都不包括e=(Vx，Vy)，且设T是一棵这样的MST由于T是连通的，因此有从Vx到Vy的路径Vx，Vy,北京大学信息学院 版权所有，转载或翻印必究 Page 81,6.6.1 Prim算法（续）,把边e=(Vx，Vy)加进树T，得到一个回路Vx，Vy，Vx上述路径Vx，Vy中必有边e=(Vp，Vq)，其中VpV*，Vq不属于V*，由条件知边的权W(e)W(e)，从回路中去掉边e，回路打开，成为另一棵生成树T”，T”包括边e=(Vx，Vy)，且各边权的总和不大于T各边权的总和,北京大学信息学院 版权所有，转载或翻印必究 Page 82,6.6.1 Prim算法（续）,因此T”是一棵包括边e的MST，与假设矛盾，即证明了我们的结论。也证明了Prim算法构造MST的方法是正确的，因为我们是从T包括任意一个顶点和0条边开始，每一步加进去的都是MST中应包括的边，直至最后得到MST。,北京大学信息学院 版权所有，转载或翻印必究 Page 83,6.6.1 Prim算法（续）,Prim算法证明过程的图示,北京大学信息学院 版权所有，转载或翻印必究 Page 84,6.6.1 Prim算法（续）,/最小支撑树的Prim算法 void Prim(Graph,北京大学信息学院 版权所有，转载或翻印必究 Page 85,6.6.1 Prim算法（续）,int v=s;G.Markv=VISITED;/开始顶点首先被标记 do/将以v为顶点，/另一顶点未被标记的边插入最小值堆H for(Edge e=G.FirstEdge(v);G.IsEdge(e);e=G.NextEdge(e)if(G.MarkG.ToVertex(e)=UNVISITED)H.Insert(e);,北京大学信息学院 版权所有，转载或翻印必究 Page 86,6.6.1 Prim算法（续）,/寻找下一条权最小的边 bool Found=false;while(!H.empty()e=H.RemoveMin();if(G.MarkG.ToVertex(e)=UNVISITED)Found=true;break;,北京大学信息学院 版权所有，转载或翻印必究 Page 87,6.6.1 Prim算法（续）,if(!Found)Print(不存在最小支撑树。);delete MST;/释放空间 MST=NULL;/MST是空数组 return;,北京大学信息学院 版权所有，转载或翻印必究 Page 88,6.6.1 Prim算法（续）,v=G.ToVertex(e);/在顶点v的标志位上做已访问的标记 G.Markv=VISITED;/将边e加到MST中 AddEdgetoMST(e,MST,MSTtag+);while(MSTtag(G.VerticesNum()-1),北京大学信息学院 版权所有，转载或翻印必究 Page 89,6.6.1 Prim算法（续）,Prim算法与Dijkstra算法十分相似，唯一区别是：Prim算法要寻找的是离已加入顶点距离最近的顶点，而不是寻找离固定顶点距离最近的顶点，所以其时间复杂度分析与Dijkstra算法相同。,北京大学信息学院 版权所有，转载或翻印必究 Page 90,6.6.2 Kruskal算法,Kruskal算法的基本思想是：对于图G=（V，E），开始时，将顶点集分为|V|个等价类，每个等价类包括一个顶点；然后，以权的大小为顺序处理各条边，如果某条边连接两个不同等价类的顶点，则这条边被添加到MST，两个等价类被合并为一个；反复执行此过程，直到只剩下一个等价类。,北京大学信息学院 版权所有，转载或翻印必究 Page 91,6.6.2 Kruskal算法（续）,对上图用Kruskal算法，其处理过程见下图,北京大学信息学院 版权所有，转载或翻印必究 Page 92,6.6.2 Kruskal算法（续）,北京大学信息学院 版权所有，转载或翻印必究 Page 93,6.6.2 Kruskal算法（续）,北京大学信息学院 版权所有，转载或翻印必究 Page 94,6.6.2 Kruskal算法（续）,/最小支撑树的Kruskal算法void Kruskal(Graph/最小支撑树边的标号,北京大学信息学院 版权所有，转载或翻印必究 Page 95,6.6.2 Kruskal算法（续）,/将图的所有边插入最小值堆H中 for(int i=0;iG.VerticesNum();i+)for(Edge e=G.FirstEdge(i);G.IsEdge(e);e=G.NextEdge(e)if(G.FromVertex(e)G.ToVertex(e)H.Insert(e);,北京大学信息学院 版权所有，转载或翻印必究 Page 96,6.6.2 Kruskal算法（续）,int EquNum=G.VerticesNum();/开始时有|V|个等价类 while(EquNum1)/合并等价类Edge e=H.RemoveMin();/获得下一条权最小的边if(e.weight=INFINITY)Print(不存在最小支撑树.“);delete MST;/释放空间 MST=NULL;/MST是空数组 return;,北京大学信息学院 版权所有，转载或翻印必究 Page 97,6.6.2 Kruskal算法（续）,int from=G.FromVertex(e);/记录该条边的信息 int to=G.ToVertex(e);if(A.differ(from,to)/如果边e的两个顶点不在一个等价类/将边e的两个顶点所在的两个等价类合并为一个 A.UNION(from,to);/将边e加到MST AddEdgetoMST(e,MST,MSTtag+);/将等价类的个数减1 EquNum-;,北京大学信息学院 版权所有，转载或翻印必究 Page 98,6.6.2 Kruskal算法（续）,使用了路径压缩，differ和UNION函数几乎是常数假设可能对几乎所有边都判断过了，则最坏情况下算法时间代价为 O(|E|log|E|)，即堆排序的时间通常情况下只找了接近顶点数目那么多边的情况下，MST就已经生成，时间代价接近于O(|V|log|E|),北京大学信息学院 版权所有，转载或翻印必究 Page 99,总结,6.1 图的基本概念6.2 图的抽象数据类型6.3 图的存储结构6.4 图的周游6.5 最短路径问题6.6 最小支撑树,
