《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第7章 图-3》由会员分享，可在线阅读，更多相关《数据结构 C++版 普通高等教育“十一五”国家级规划教材 教学课件 ppt 杨秀金 第7章 图-3（39页珍藏版）》请在金锄头文库上搜索。
1、1,第7章 图,第3讲,第6章 树与二叉树,2,本章分为（45）讲,第1讲 7.1 图的基本概念 7.2 图的存储结构 -7.2.1,第3讲 7.4 图的最小生成树 7.5 最短路径,第2讲 7.4 图的存储结构-7.2.2, 7.2.3, 7.2.4 7.3 图的遍历与连通性,第4讲 7.6 拓扑排序与关键路径题 小结,供教师参考,3,7.4 图的最小生成树,一个连通图的生成树是图的极小连通子图，它包含原图中的所有顶点和尽可能少的边（n个顶点、n1条边），这意味着对于生成树来说，再去掉一条边，就会使生成树变成非连通图；再增加一条边，就会形成图中的一个回路。 使用不同的遍历图的方法，可以得到不
2、同的生成树，如DFS 生成树和BFS生成树；从不同的顶点出发，也可能得到不同的生成树。 从生成树的定义可知，对有n个顶点的无向连通图，无论它的生成树的形状如何，一定有且仅有n1条边。,4,7.4.1 最小生成树的概念,如果无向连通图是一个网（或称带权图），那么它的所有生成树中必有一棵边的权值总和最小的生成树，称这棵生成树为最小代价生成树，简称最小生成树。 许多应用问题都是求无向连通图的最小生成树问题。例如，在n个城市之间建立通信网络，至少要架设n1条线路，这时自然会考虑：如何做才能使得造价最少？,5,n个城市之间的通信问题：,用图的顶点表示n个城市，用边表示两城市之间架设的线路，用边上的权值表
3、示该线路的造价，就可以建立一个通信网络。 对于这样一个有n个顶点的网络，可以有不同的生成树，每一棵生成树都可以构成通信网络。人们希望能够根据各条边上的权值，选择一棵总造价最小的生成树，这就是构造连通网的最小（代价）生成树MST（Minimum Cost Spanning Tree）的问题。,6,MST性质,构造最小生成树的算法利用了一种称为MST的性质： 设N = (V,E)是一个连通网，U是顶点集的一个非空子集，若（u, v）是一条具有最小权值的边，其中uU，而vVU，则存在一棵含边（u, v）的最小生成树。 利用MST性质构造最小生成树的两个典型算法：普里姆（Prim）算法和克鲁斯卡尔（K
4、ruskal）算法。,7,7.4.2 普里姆（Prim）算法,假设G= (V，E) 是一个网络。 Prim算法的基本思想： 设T= (U，TE)为欲构造的最小生成树。首先指定起始顶点u0 ，它允许是图中任一顶点。初始化顶点集U=u0，边集为空TE=。 重复下述操作：在所有uU，vVU的边（u, v）E中，选择一条权值最小的边（u, v）并入TE，同时将v并入U，直到U=V为止。 容易看出，上述过程所求得的T= (U,TE)是G的一棵最小生成树。,8,普里姆（Prim）方法手工实现图例,注意：首先任意指定一个始发顶点，必须明确； 选择权值最小的边，它的一个顶点必须是属于U集，另一个顶点必须不属于
5、U集。 直到U集有n个顶点，TE集有n-1条边。,教师需 详细讲解这部 分内容。,9,连通网用邻接矩阵图类AdjMWGraph表示，Edge是带权值的矩阵。权值用一个很大数MAX表示不存在边。 使用一个辅助数组mintree，每个数组元素表示一条边的信息。最终形成的最小生成树就存在该数组之中。 该数组元素的类型如下： struct MinSpanTree int begin, end; /边的起点 和终点 float length; /边的权值 n个顶点的连通网的最小生成树有n1条边： MinSpanTree mintreen-1;,普里姆（Prim）算法,教师自行决定 是否讲算法的函数代码。
6、 建议不讲。,10,普里姆算法7.5,void Prim (AdjMWGraph / G.Edge是连通网的带权邻接矩阵 ,11,for (int k=0; kn-1; k+) /求n-1条边 min=MAX; for (int j=k; jn-1; j+) /求最小权值边 if (mintreej.lengthmin ) min=mintreej.length; m=j; e=mintreem; mintreem=mintreek; mintreek=e; /最小边移至前端 v=mintreek.end; /v并入U集 for (j=k+1; jn-1; j+) /新顶点v并入U，更新min
7、tree int d= G.Edge v-1mintreej.end-1 if (dmintreej.length) mintreej.length=d; mintreej.begin=v; /for j / for k,12,普里姆算法7.5,for (int j=1;jn; j+) cout”n “mintreej.begin” ”min treej.end” ”mintreej.length; /Prim 算法主要是一个两重循环，其算法的时间复杂度为O(n2)。 由于该算法的时间复杂度只与网中顶点的个数有关，而与网中边的条数无关，所以用于顶点个数不是很多而边稠密的网时，时间效率比较高。,
8、13,7.4.3 克鲁斯卡尔（Kruskal）算法,克鲁斯卡尔算法是一种按照网中边的权值递增的顺序构造最小生成树的方法。算法思想： 设无向连通网G=(V，E)。 设网G的最小生成树T由顶点集合和边的集合构成，其初值为T= (V，)，即初始时最小生成树T只由网G中顶点集合V组成，边集为空。 这样，最小生成树T的每个顶点各自构成一个连通分量，即存在n个连通分量。,14,然后，按照边的权值递增的顺序考察网G中的边集E中的各条边： 若被考察的边的两个顶点属于T的两个不同的连通分量，且权值最小。则将此边加入到最小生成树T，同时把两个连通分量连接为一个连同分量； 若被考察的边的两个顶点属于T的同一个连通分
9、量，则将此边舍去。 如此下去，T中的连通分量数逐步减少，当连通分量个数为时，T中这个唯一的连通分量即为网G的一棵最小生成树。,15,克鲁斯卡尔（Kruskal）算法手工实现图例：,教师需 详细讲解这部 分内容。,注意：首先找权值最小的边； 选择剩余边（且两个顶点不属同一个连同分量）权值最小的边；直到成为一个连通图。,16,克鲁斯卡尔算法思想分析：,克鲁斯卡尔算法主要包括两部分：首先是对网G中e条边的权值进行排序，其次是判断新选取最小边的两个顶点是否属于同一个连通分量。 排序算法时间复杂度最好可以达O(elog2e)。 判断新选取的边的两个顶点是否属于同一个连通分量问题的时间复杂度在最坏情况下为
10、O(n)。 克鲁斯卡尔算法的时间复杂度主要由排序方法决定，为O(elog2e)。当网的顶点个数多、而边的条数少时，使用本算法构造最小生成树效果较好。,17,7.5 最短路径,若要建立一个交通信息系统，可用一个带权的图来表示一个交通网络。用图的顶点表示地点，用图中的边表示两地之间的交通路线，每条边上所附的权值表示该路线的长度或途中的时间、费用不相同等情况时，交通网络用带权有向图表示。用户一般会关心两类问题： （1）从A地到B地途中，中转次数最少的线路； （2）从A地到B地途中，距离、时间、费用最小的线路。,18,第1个问题是简单的最短路径问题，只需从A出发，对图作广度优先搜索，直到遇到B为止。在
11、所得的生成树中，从A到B的路径，就是途中中转次数最少的线路。 第2个问题是用户最关心的问题，它关系到途中的时间、费用等。 最短路径问题是：如果从图中某一顶点到达另一顶点的路径可能不止一条，如何找到一条路径使得沿此路径上各边权值总和（称为路径长度）最小。称始发顶点为源点（Sourse），到达顶点为终点（Distination）。 本节只讨论有向网络的最短路径，并假定所有的权为非负实数。,19,7.5.1单源顶点最短路径,单源顶点最短路径问题，对于给定的一个带权的有向图G，假设源点为v，求从v到G中其余各顶点的最短路径。 为求最短路径，迪杰斯特拉（Dijkstra）提出了按路径长度的递增次序，逐步
12、产生最短路径的算法。,20,例如，从v0到v2有两条不同路径： （v0，v1，v2） 路径长度90 （v0，v3，v4，v2）路径长度80，最短路径。,21,迪杰斯特拉（Dijkstra）算法思想：,设集合S存放已经求出的最短路径的终点。初始状态时，集合S中只有一个源点，不妨设为v0。 以后每求得一条最短路径（v0，vk），就将vk加入到集合S中，直到全部顶点全部都加入到集合S中为止。,22,为此，引入一个辅助数组dist，它的每一个分量disti表示当前从源点v0到终点vi的最短路径长度。初始状态： 若从源点v0到vi有边，则disti为该边权值； 若从v0到vi没有边，则disti为MAX
13、NUM。 显然，路径长度为： dist j = min dist i viV-v0 的路径是从v0出发的最短路径，即为（v0, vj ），随即将vj加入到集合S中。,23,一般情况，下一条长度最短的路径（v0,vk）长度必为: distk= mindistiviV-S 在每次求得一条最短路径之后，其终点vk加入到集合S中，然后对所有的viV-S，修改其它当前最短路径长度： disti= min disti，distk+Edgeki ， 其中Edgeki是边（vk, vi）上的权值。 （v0到vi直接距离disti和v0到 vk 再到 vi间接距离，取其中小值。）,24,带权有向图的邻接矩阵类：
14、,const int NumVex=10; /图中最大顶点个数 class DijGraph private: float EdgeNumVexNumVex; /图的邻接矩阵 float distNumVex; /v0到其他顶点的最短路径 int pathNumVex; /在最短路径上该顶点的前一顶点 int SNumVex; /存放已求得的在最短路径上的顶点集合 int n; public: void ShorttestPath_Dijkstra(int,int); int choose(int); ;,25,void DijGraph:ShorttestPath_Dijkstra( int
15、 v) for ( int i=0; in; i+ ) /dist,path,S的初始化 disti=Edgevi; Si=0; if ( i!=v /自己到自己无路径,求从源点v到其余各顶点的最短路径长度,26,for ( i=0; in; i+ ) /求其余n-1个顶点的最短路径 float min=MAXNUM; int u=v; for ( int j=0; jn; j+ ) /选择当前不在集合S中具有最短路径的顶点u if ( !Sj /for i / 函数结束,27,例如，求带权有向图从v0到其余各顶点的最短路径，表格中是迪杰斯特拉算法中各辅助数组的变化。,28,从表格可知path4=3(v3)，path3=0(v0),表示v4的前一顶点为v3， v3的前一顶点为v0，得最短路径为(v0,v3,v4)，路径长度dist4=40。 同理从path2=4,path4=3,path3=0最短路径为(v0,v3,v4,v2)，路径长度dist2=80。,29,7.5.2 每对顶点之间的最短路径,求出每对顶点之间的最短路径，解决问题的一个方法是：分别以每个顶点为源点，重复执行迪杰斯特拉算法。这样就可求得每对顶点之间的最短路径及最短路
