数据结构[C][第07章.ppt

《数据结构[C][第07章.ppt》由会员分享，可在线阅读，更多相关《数据结构[C][第07章.ppt（105页珍藏版）》请在三一办公上搜索。

1、2023/11/14,1,第7章 图,本章学习内容,7.1 图的基本概念,7.2 图的存储结构,7.3 图的遍历,7.4 生成树和最小生成树,7.5 最短路径,7.6 有向无环图及其应用,2023/11/14,2,7.1.1 图的定义,7.1 图的基本概念,图是由顶点集V和顶点间的关系集合E（边的集合）组成的一种数据结构，可以用二元组定义为：G=(V,E)。,例如，对于图7-1所示的无向图G1和有向图G2，它们的数据结构可以描述为：G1=(V1,E1)，其中V1=a,b,c,d，E1=(a,b)(a,c),(a,d),(b,d),(c,d)，而G2=(V2,E2)，其中V2=1,2,3，E2=

2、,。,（a）无向图G1（b）有向图G2 图7-1 无向图和有向图,2023/11/14,3,7.1.2 图的基本术语,1有向图和无向图,在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。图7-1中，G1为无向图，G2为有向图。,在无向图中，一条边（x,y）与（y,x）表示的结果相同，用圆括号表示，在有向图中，一条边与表示的结果不相同，故用尖括号表示。表示从顶点x发向顶点y的边，x为始点，y为终点。有向边也称为弧，x为弧尾，y为弧头，则表示为一条弧；而表示y为弧尾，x为弧头的另一条弧。,2023/11/14,4,2完全图、稠密图、稀疏图,具有n个顶点，n(n-1)/2条

3、边的图，称为完全无向图；具有n个顶点，n(n-1)条弧的有向图，称为完全有向图。完全无向图和完全有向图都称为完全图。,对于一般无向图，顶点数为n，边数为e，则0en(n-1)/2。,对于一般有向图，顶点数为n，弧数为e，则0en(n-1)。,当一个图接近完全图时，称它为稠密图，相反地，当一个图中含有较少的边或弧时，称它为稀疏图。,3度、入度、出度,在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度；一个顶点依附的弧尾数目，称为该顶点的出度；某个顶点的入度和出度之和称为该顶点的度。,2023/11/14,5,另外，若图中有n个顶点，e条边或弧

4、，第i个顶点的度为di，则有e=。,例如，对图7-1，G1中顶点a，b，c，d的度分别为3，2，2，3，G2中顶点1，2，3的出度分别为2，1，1，而它们的入度分别为1，1，2，故顶点1，2，3的度分别为3，2，3。,4子图,若有两个图G1和G2，G1=(V1,E1)，G2=(V2,E2)，满足如下条件：V2V1，E2 E1，即V2为V1的子集，E2为E1的子集，称图G2为图G1的子图。,图和子图的示例具体见图7-2。,（a）图G（b）图G的两个子图 图7-2 图与子图示例,2023/11/14,6,5权,在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离、耗费等，带权图

5、一般称为网。,带权图的示例具体见图7-3。,（a）无向网（b）有向网 图7-3 无向带权图和有向带权图,2023/11/14,7,6连通图和强连通图,在无向图中，若从顶点i到顶点j有路径，则称顶点i到顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。,连通图和非连通图示例见图7-4。,（a）连通图,（b）非连通图,图7-4 连通图和非连通图,2023/11/14,8,在有向图中，若从顶点i到顶点j有路径，则称从顶点i到顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图。,强连通图和非强连通图示例见图7-5。,（a）强连通图,

6、（b）非强连通图,图7-5 强连通图和非强连通图,2023/11/14,9,7连通分量和强连通分量,无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。,对于图7-4中的非连通图，它的连通分量见图7-6。,图7-6 图7-4（b）的连通分量,2023/11/14,10,有向图中，极大的强连通子图为该图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。,对于图7-5中的非强连通图，它的强连通分量见图7-7。,图7-7 图7-5（b）的强连通分量,2023/11/14,11,8路径、回路,在无

7、向图G中，若存在一个顶点序列Vp，Vi1，Vi2，Vin，Vq,使得(Vp,Vi1)，(Vi1,Vi2)，(Vin,Vq)均属于E(G)，则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。,9有根图,在一个有向图中，若从顶点V有路径可以到达图中的其他所有顶点，则称此有向图为有根图，顶点V称做图的根。,10生成树、生成森林,连通图的生成树是一个极小连通子图，它包含图中全部n个顶点和n-1条不构成回路的边。非连通图的生成树则组成一个生成森

8、林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。,2023/11/14,12,7.2 图的存储结构,由于图是一种多对多的非线性关系，因此，无法用数据元素在存储区中的物理位置来表示元素之间的关系，故不能用顺序存储结构。下面将介绍常用的三种存储结构：邻接矩阵、邻接表和邻接多重表。,7.2.1 邻接矩阵,1图的邻接矩阵表示,在邻接矩阵表示中，除了存放顶点本身的信息外，还用一个矩阵表示各个顶点之间的关系。若(i,j)E(G)或i,jE(G)，则矩阵中第i行 第j列元素值为1，否则为0。,图的邻接矩阵定义为：,1 若(i,j)E(G)或i,jE(G)Aij=0 其他情形,2023/11/1

9、4,13,例如，对图7-8所示的无向图和有向图，它们的邻接矩阵见图7-9。,（a）无向图G3（b）有向图G4 图7-8 无向图G3及有向图G4,（a）G3的邻接矩阵（b）G4的邻接矩阵 图7-9 邻接矩阵表示,2023/11/14,14,2从无向图的邻接矩阵可以得出如下结论,（1）矩阵是对称的；,（2）第i行或第i 列1的个数为顶点i的度；,（3）矩阵中1的个数的一半为图中边的数目；,（4）很容易判断顶点i和顶点j之间是否有边相连（看矩阵中i行j列值是否为1）。,3从有向图的邻接矩阵可以得出如下结论,（1）矩阵不一定是对称的；,（2）第i 行中1的个数为顶点i的出度；,（3）第j列中1的个数为

10、顶点j的入度；,（4）矩阵中1的个数为图中弧的数目；,（5）很容易判断顶点i 和顶点j 是否有弧相连。,2023/11/14,15,4网的邻接矩阵表示,类似地可以定义网的邻接矩阵为：,wij 若(i,j)E(G)或i,jE(G)Aij=0若i=j 其他情形,网及网的邻接矩阵见图7-10。,（a）网G5（b）网G5的邻接矩阵示意图 图7-10 网及邻接矩阵示意图,2023/11/14,16,5图的邻接矩阵数据类型描述,图的邻接矩阵数据类型描述如下:,const int n=maxn；/图中顶点数 const int e=maxe；/图中边数class graph public:elemtype

11、vn+1;/存放顶点信息v1,v2,vn，不使用v0存储空间int arcsn+1n+1/邻接矩阵/成员函数说明及定义;,2023/11/14,17,6建立无向图的邻接矩阵,void graph:creatadj(graph,该算法的时间复杂度为O(n2)。,2023/11/14,18,7建立有向图的邻接矩阵,void graph:creatadj(graph,该算法的时间复杂度为O(n2)。,2023/11/14,19,8建立无向网的邻接矩阵,void graph:creatadj(graph,该算法的时间复杂度为O(n2)。,2023/11/14,20,9建立有向网的邻接矩阵,void g

12、raph:creatadj(graph,该算法的时间复杂度为O(n2)。,2023/11/14,21,若要将得到的邻接矩阵输出，可以使用如下的语句段：,for(int i=1;i=n;i+)for(int j=1;j=n;j+)coutg.arcsij;coutendl;,7.2.2 邻接表,1图的邻接表表示,将每个结点的边用一个单链表链接起来，若干个结点可以得到若干个单链表，每个单链表都有一个头结点，为将所有头结点联系起来组成一个整体，所有头结点可看成一个一维数组，称这样的链表为邻接表。,2023/11/14,22,例如，图7-8所示的无向图G3和有向图G4的邻接表如图7-11所示。,（a）

13、无向图G3的邻接表,（b）有向图G4的邻接表,（c）有向图G4的逆邻接表,图7-11 邻接表示例,2023/11/14,23,2从无向图的邻接表可以得到如下结论,（1）第i个链表中结点数目为顶点i的度；,（2）所有链表中结点数目的一半为图中边数；,（3）占用的存储单元数目为n+2e。,3从有向图的邻接表可以得到如下结论,（1）第i个链表中结点数目为顶点i的出度；,（2）所有链表中结点数目为图中弧数；,（3）占用的存储单元数目为n+e。,从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在图7-11（c）中已经给出，从该图中可知。

14、有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。,2023/11/14,24,4图的邻接表数据类型描述,图的邻接表数据类型描述如下：,const int n=maxn；/maxn表示图中最大顶点数const int e=maxe；/maxe表示图中最大边数class link/定义链表类型 public:elemtype data;link*next;class node/定义邻接表的表头类型 public:link an+1;void creatlink(node,在本章中，为描述问题方便直观，我们将elemtype 类型设定为int类型，以此代表图中顶点的序号。

15、,2023/11/14,25,5无向图的邻接表建立,void node:creatlink(node,该算法的时间复杂度为O(n+e)。,2023/11/14,26,6有向图的邻接表建立,void node:creatlink(node,该算法的时间复杂度为O(n+e)。,2023/11/14,27,7网的邻接表的数据类型描述,网的邻接表的数据类型可描述如下：,const int n=maxn；/maxn表示网中最大顶点数const int e=maxe；/maxe表示网中最大边数class link/定义链表类型 public:elemtype data;float w;/定义网上的权值类型

16、为浮点型 link*next;class node/定义邻接表的表头类型 public:link an+1;void creatlink(node,2023/11/14,28,8无向网的邻接表建立,void node:creatlink(node,该算法的时间复杂度为O(n+e)。,2023/11/14,29,9有向网的邻接表建立,void node:creatlink(node,该算法的时间复杂度为O(n+e)。,2023/11/14,30,另外，请注意上面的算法中，建立的邻接表不是惟一的，与你从键盘输入边的顺序有关，输入边的顺序不同，得到的链表也不同。,若要将得到的邻接表输出，可以使用如下

17、的语句：,for(int i=1;i;while(p-next!=NULL)coutdata;p=p-next;coutdataendl;,2023/11/14,31,7.2.3 邻接多重表,在无向图的邻接表中，每条边(Vi,Vj)由两个结点表示，一个结点在第i个链表中，另一个结点在第j个链表中，当需要对边进行操作时，就需要找到表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表比较方便。,在邻接多重表中，每条边用一个结点表示，每个结点由五个域组成，其结点结构为：,其中Mark为标志域，用来标记这条边是否被访问过，i和j域为一条边的两个顶点，next1 和next2为两个指针域

18、，分别指向依附于i顶点的下一条边和j顶点的下一条边。而表头与邻接表的表头类似。,2023/11/14,32,邻接多重表的形式见图7-12。,（a）无向图G6（b）G6的邻接多重表 图7-12 邻接多重表示例,2023/11/14,33,7.3 图的遍历,和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图中所有的顶点，但是，在图中有回路，从图中某一顶点出发访问图中其他顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到，因此，图的遍历较树的遍历更复杂。我们可以设置一个全局型标志数组visit

19、ed来标志某个顶点是否被访过，未访问的值为false，访问过的值为true。根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索遍历和广度优先搜索遍历。,2023/11/14,34,7.3.1 深度优先搜索遍历,1深度优先搜索思想,深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下：,（1）首先访问顶点i，并将其访问标记置为访问过，即visitedi=true；,（2）然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visitedj=true，然后从j

20、开始重复此过程，若j已访问，再看与i有边相连的其他顶点；,（3）若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才的过程，直到图中所有顶点都被访问完为止。,2023/11/14,35,例如，对图7-13所示的无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出其中三种，其他可作类似分析写出来。,图7-13 无向图G7,在无向图G7中，从顶点1出发的深度优先搜索遍历序列（列举三种）为：,1,2,4,8,5,6,3,7,1,2,5,8,4,7,3,6,1,3,6,8,7,4,2,5,2023/11/14,36,2连通图的深度优先搜索,若图是连通的或强连通的，则从图中某一

21、个顶点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。,另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不惟一的。但是若我们给定图的存储结构，则从某一顶点出发的遍历结果应是惟一的。,（1）用邻接矩阵实现图的深度优先搜索,以图7-13中无向图G7为例，来说明算法的实现，G7的邻接矩阵见图7-14。,图7-14 无向图G7的邻接矩阵,2023/11/14,37,算法描述如下：,#include#define elemtype intconst int n=8;/图中顶点数 const int e=10;/图中边数bool visitedn+1;,class graph pub

22、lic:elemtype vn+1;/存放顶点信息v1,v2,vn，不使用v0存储空间int arcsn+1n+1;/邻接矩阵void creatadj(graph,2023/11/14,38,void graph:creatadj(graph,2023/11/14,39,void graph:dfs(graph g,int i)/从顶点i 出发实现深度优先搜索遍历 int j;coutg.vi;/输出访问顶点 visitedi=true;/全局数组访问标记置1表示已经访问 for(j=1;j=n;j+)if(g.arcsi j=1),void main()graph g;g.creatadj

23、(g);for(i=1;i=n;i+)visitedi=false;g.dfs(g,1);/从顶点1出发访问,2023/11/14,40,用上述算法和无向图G7，可以描述从顶点1出发的深度优先搜索遍历过程，示意图见图7-15，其中实线表示下一层递归调用，虚线表示递归调用的返回。,图7-15 邻接矩阵深度优先搜索示意图,从图7-15中，可以得到从顶点1的遍历结果为1,2,4,8,5,6,3,7。同样可以分析出从其他顶点出发的遍历结果。,2023/11/14,41,（2）用邻接表实现图的深度优先搜索,仍以图7-13中无向图G7为例，来说明算法的实现，G7的邻接表见图7-16,图7-16 G7的邻接

24、表,2023/11/14,42,算法描述如下：,#include#define elemtype intconst int n=8;/n表示图中最大顶点数const int e=10;/e为图中最大边数bool visitedn+1;,class link/定义链表类型 public:elemtype data;link*next;,2023/11/14,43,class node/定义邻接表的表头类型 public:link an+1;void creatlink(node,void node:creatlink(node,2023/11/14,44,for(k=1;kij;/输入一条边(i

25、,j)s=new link;/申请一个动态存储单元s-data=j;s-next=g.ai.next;g.ai.next=s;s=new link;s-data=i;s-next=g.aj.next;g.aj.next=s;,2023/11/14,45,void node:dfs1(node g,int i)link*p;coutdata)dfs1(g,p-data);p=p-next;,void main()node g;g.creatlink(g);for(i=1;i=n;i+)visitedi=false;g.dfs1(g,1);/从顶点1访问,2023/11/14,46,用刚才的算法及

26、图7-16，可以描述从顶点7出发的深度优先搜索遍历示意图，见图7-17，其中实线表示下一层递归，虚线表示递归返回，箭头旁边的数字表示调用的步骤。,图7-17 邻接表深度优先搜索示意图,于是，从顶点7出发的深度优先搜索遍历序列，从图7-17中可得出为7，3，1，2，4，8，5，6。从其他顶点出发的深度优先搜索序列，请读者自已写出。,2023/11/14,47,3非连通图的深度优先搜索,若图是非连通图或非强连通图，则从图中某一个顶点出发，不能用深度优先搜索访问到图中所有顶点，而只能访问到一个连通子图（即连通分量）或只能访问到一个强连通子图（即强连通分量）。这时，可以在每个连通分量或每个强连通分量中

27、都选一个顶点，进行深度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图的遍历结果。,遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的深度优先搜索遍历算法即可。具体实现如下：,for(int i=1;i=n;i+)if(!visitedi)dfs(i);,或者为：for(int i=1;i=n;i+)if(!visitedi)dfs1(i);,2023/11/14,48,7.3.2 广度优先搜索遍历,1广度优先搜索的思想,广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜

28、索的基本思想是：,（1）首先访问顶点i，并将其访问标志置为已被访问，即visitedi=true；,（2）接着依次访问与顶点i有边相连的所有顶点W1，W2，Wt；,（3）然后再按顺序访问与W1，W2，Wt有边相连又未曾访问过的顶点；,（4）依此类推，直到图中所有顶点都被访问完为止。,2023/11/14,49,例如，对图7-13所示的无向图G7，从顶点1出发的广度优先搜索遍历序列可有多种，下面仅给出其中三种，其他可作类似分析。,在无向图G7中，从顶点1出发的广度优先搜索遍历序列（列举三种）为：,1,2,3,4,5,6,7,8,1,3,2,7,6,5,4,8,1,2,3,5,4,7,6,8,这对

29、于连通图是可以办到的，但若是非连通图，则只须对每个连通分量都选一顶点作开始点，都进行广度优先搜索，则可以得到非连通图的遍历。,2023/11/14,50,2连通图的广度优先搜索,（1）用邻接矩阵实现图的广度优先搜索遍历,仍以图7-13中无向图G7及图7-14所示的邻接矩阵来说明对无向图G7的遍历过程，算法描述如下：,#include#define elemtype intconst int n=8;/图中顶点数 const int e=10;/图中边数bool visitedn+1;,class graph public:elemtype vn+1;/存放顶点信息v1,v2,vn，不使用v0存

30、储空间int arcsn+1n+1;/邻接矩阵void creatadj(graph,2023/11/14,51,void graph:creatadj(graph,2023/11/14,52,void graph:bfs(graph g,int i)/从顶点i出发实现图的广度优先搜索遍历 int qn+1;/q为队列 int f,r,j;/f、r分别为队列头、尾指针 f=r=0;/设置空队列 coutg.vi;/输出访问顶点 visitedi=true;/全局数组标记置true表示已经访问 r+;qr=i;/入队列 while(fr)f+;i=qf;/出队列for(j=1;j=n;j+)if

31、(g.arcsij=1),void main()graph g;g.creatadj(g);for(i=1;i=n;i+)visitedi=false;g.bfs(g,1);/从顶点1出发实现图的广度优先搜索遍历,2023/11/14,53,（2）用邻接表实现图的广度优先搜索遍历,仍以无向图G7及图7-16所示的邻接表来说明邻接表上实现广度优先搜索遍历的过程。具体算法描述如下：,#include#define elemtype intconst int n=8;/maxn表示图中最大顶点数const int e=10;/maxe表示图中最大边数bool visitedn+1;,class li

32、nk/定义链表类型 public:elemtype data;link*next;,class node/定义邻接表的表头类型 public:link an+1;void creatlink(node,2023/11/14,54,void node:creatlink(node,for(k=1;kij;/输入一条边(i,j)s=new link;/申请一个动态存储单元s-data=j;s-next=g.ai.next;g.ai.next=s;s=new link;s-data=i;s-next=g.aj.next;g.aj.next=s;,2023/11/14,55,void node:bfs

33、1(node g,int i)int qn+1;/定义队列 int f,r;link*p;/p为搜索指针 f=r=0;coutg.ai.data;visitedi=true;r+;qr=i;/进队,while(fdata)coutdata.datadata=true;r+;qr=p-data;p=p-next;,2023/11/14,56,void main()node g;g.creatlink(g);for(i=1;i=n;i+)visitedi=false;g.bfs1(g,1);/从顶点1出发实现图的广度优先搜索遍历,根据该算法及图7-16，可以得到图G7的广度优先搜索遍历序列，若从顶

34、点1出发，广度优先搜索遍历序列为：1，2，3，4，5，6，7，8；若从顶点7出发，广度优先搜索遍历序列为：7，3，8，1，6，4，5，2；从其他顶点出发的广度优先搜索遍历序列，可根据同样类似方法分析得到。,2023/11/14,57,3非连通图的广度优先搜索,若图是非连通图或非强连通图，则从图中某一个顶点出发，不能用广度优先搜索遍历访问到图中所有顶点，而只能访问到一个连通子图（即连通分量）或只能访问到一个强连通子图（即强连通分量）。这时，可以在每个连通分量或每个强连通分量中都选一个顶点，进行广度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图或非强连通图的广

35、度优先搜索遍历序列。,遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的广度优先搜索遍历算法即可。具体可以表示如下：,for(int i=1;i=n;i+)for(int i=1;i=n;i+)if(!visitedi)或 if(!visitedi)g.bfs(g,i);g.bfs1(g,i);,2023/11/14,58,7.4 生成树和最小生成树,7.4.1 基本概念,1生成树,在图论中，常常将树定义为一个无回路连通图。例如，图7-18中的两个图就是无回路的连通图。乍一看它似乎不是树，但只要选定某个顶点做根并以树根为起点对每条边定向，就可以将它们变为通常的树。,图7

36、-18 两个无回路的连通图,2023/11/14,59,在一个连通图中，有n个顶点，若存在这样一个子图，含有n个顶点，n-1条不构成回路的边，则这个子图称为生成树，或者定义为：一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图为图G的生成树。,由于n个顶点的连通图至少有n-1条边，而所有包含n-1条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图。所谓极小是指边数最少。若在生成树中去掉任何一条边，都会使之变为非连通图；若在生成树上任意增加一条边，就会构成回路。,那么，对给定的连通图，如何求得它的生成树呢？回到我们前面提到的图的遍历，访问过图中一个顶点后，要访问下一

37、个顶点，一般要求两个顶点有边相连，即必须经过图中的一条边，要遍历图中n个顶点且每个顶点都只遍历一次，则必须经过图中的n-1条边，这n-1条边构成连通图的一个极小连通子图，所以它是连通图的生成树。由于遍历结果可能不惟一，所以得到的生成树也是不惟一的。,2023/11/14,60,要求得生成树，可考虑用刚才讲过的深度优先搜索遍历算法及广度优先搜索遍历算法。对于深度优先搜索算法DFS或DFS1，由DFS(i)递归到DFS(j)，中间必经过一条边(i,j)，因此，只需在DFS(j)调用前输出这条边或保存这条边，即可求得生成树的一条边，整个递归完成后，则可求得生成树的所有边。对于广度优先搜索算法BFS或

38、BFS1，若i出队，j入队，则(i,j)为一条树边。因此，可以在算法的if 语句中输出这条边，算法完成后，将会输出n-1条边，也可求得生成树。,由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。,2023/11/14,61,图7-13中无向图G7的两种生成树如图7-19所示。,（a）深度优先生成树（b）广度优先生成树 图7-19 两种生成树示意图,若一个图是强连通的有向图，同样可以得到它的生成树。生成树可以利用连通图的深度优先搜索遍历或连通图的广度优先搜索遍历算法得到。,2023/11/14,62,2生成森林,若一个图是非连通图或非强连通图

39、，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，得到的不是生成树，而是生成森林。且若非连通图有n 个顶点、m个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。,生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算法得到。,3最小生成树,在一般情况下，图中的每条边若给定了权值，这时，我们所关心的不是生成树，而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树。,下面将介绍求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。,2023/11/14,63,7.4.2 普里姆（pri

40、m）算法,1普里姆算法思想,下面仅讨论无向网的最小生成树问题。,普里姆算法的思想是：在图中任取一个顶点k作为开始点，令集合U=k，集合W=V-U，其中V为图中所有顶点集合，然后找出：一个顶点在集合U中，另一个顶点在集合W中的所有的边中，权值最短的一条边，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集为止。求解过程参见下面的图7-20各步骤。,2023/11/14,64,（a）无向网（b）u=1 w=2,3,4,5,6,（c）u=1,3 w=2,4,5,6（d）u=1,

41、3,6 w=2,4,5,2023/11/14,65,（e）u=1,3,6,4 w=2,5（f）u=1,3,6,4,2 w=5,（g）u=1,3,6,4,2,5 w=图7-20 prim算法构造最小生成树的过程,2023/11/14,66,2普里姆算法实现,普里姆算法的算法实现，可描述如下（假设网用邻接矩阵作存储结构，与图的邻接矩阵类似，只是将0变为，1变为对应边上权值，而矩阵中对角线上的元素值为0，本算法参照的示例为图7-20（a）中的无向网）：,#include const int n=6;/定义网中顶点数const int e=10;/定义网中边数 class edgeset/定义一条生成

42、树的边 public:int fromvex;/边的起点 int endvex;/边的终点 int weight;/边上的权值;,2023/11/14,67,class tree public:int sn+1n+1;/网的邻接矩阵edgeset ctn+1;/最小生成树的边集void prim(tree,void tree:prim(tree,2023/11/14,68,for(k=2;k=n;k+)min=32767;m=k-1;for(j=k-1;jn;j+)/找权值最小的树边 if(t.ctj.weightmin)min=t.ctj.weight;m=j;edgeset temp=t.

43、ctk-1;t.ctk-1=t.ctm;t.ctm=temp;j=t.ctk-1.endvex;,for(i=k;in;i+)/重新修改树边的距离 t1=t.cti.endvex;w=t.sjt1;if(wt.cti.weight)/原来的边用权值较小的边取代 t.cti.weight=w;,2023/11/14,69,t.cti.fromvex=j;,void main()int j,w;tree t;for(int i=1;i=n;i+)for(int j=1;j=n;j+)if(i=j)t.sij=0;else t.sij=32767;/若(i,j)边上无权值，用32767来代替,for

44、(int k=1;kijw;coutendl;t.sij=w;t.sji=w;,2023/11/14,70,t.prim(t);/用普里姆算法求最小生成树 for(i=1;in;i+)/输出n-1条生成树的边 coutt.cti.fromvex;coutt.cti.endvex;coutt.cti.weightendl;,该算法的时间复杂度为O(n2)，与边数e无关。,用普里姆算法求得图7-20（a）中的无向网的生成树，结果如图7-21所示。,图7-21 普里姆算法求解的结果,2023/11/14,71,7.4.3 克鲁斯卡尔（kruskal）算法,1克鲁斯卡尔算法的基本思想,克鲁斯卡尔算法的

45、基本思想是：将图中所有边按权值递增顺序排列，依次选定权值较小的边，但要求后面选取的边不能与前面所有选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。,例如，对图7-20（a）中的无向网，用克鲁斯卡尔算法求最小生成树的过程见下面的图7-22各步骤。,（a）选第1条边（b）选第2条边,2023/11/14,72,（c）选第3条边（d）选第4条边,（e）选第5条边（不能选(1,4)边，因为会构成回路，但可选(2,3)或(5,3)中之一）图7-22 克鲁斯卡尔算法求最小生成树的过程,2023/11/14,73,2克鲁斯卡尔算法实现,本算法参照的示例

46、为图7-20（a）中的无向网#include const int n=6;const int e=10;class edgeset/定义一条边 public:int fromvex;int endvex;int weight;,class tree/定义生成树 public:edgeset cn;/存放生成树边edgeset gee+1;/存放网中所有边int sn+1n+1;/s为一个集合，一行元素si0sin表示一个集合/若sit=1，则表示顶点t属于该集合，否则不属于该集合void kruska(tree,2023/11/14,74,void tree:kruska(tree/记录一条边

47、的两个顶点所在集合的序号,while(kn)for(i=1;i=n;i+)for(j=1;j=n;j+)if(t.ged.fromvex=j),2023/11/14,75,if(m1!=m2)t.ck=t.ged;k+;for(j=1;j=n;j+)t.sm1j=t.sm1j|t.sm2j;/求出一条边后，合并两个集合 t.sm2j=0;/另一个集合置为空 d+;,void main()tree t;for(int i=1;it.gei.fromvex;cint.gei.endvex;cint.gei.weight;t.kruska(t);for(i=1;in;i+)/输出最小生成树的边的起点

48、、终点及权值 coutt.ci.fromvex;coutt.ci.endvex;coutt.ci.weightendl;,2023/11/14,76,利用上述算法实现时，要求输入的网中的边上权值必须为从小到大排列。例如，对图7-23（a）的无向网，输入的值顺序见图7-23（b），通过算法调用得到的最小生成树的树边见图7-24。,（a）无向网,（b）用克鲁斯卡尔算法求最小生成树的输入边的顺序,图7-23 无向网及用克鲁斯卡尔算法求最小生成树的输入边的顺序,图7-24 用克鲁斯卡尔算法求出的图7-23（a）的最小生成树的树边,2023/11/14,77,7.5 最短路径,交通网络中常常提出这样的问

49、题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短?交通网络可用带权图来表示。顶点表示城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。,另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路（从其他顶点达到）。路径上的开始顶点（出发点）称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。,2023/11/14,78,7.5.1 单源点最短路径,1单源点最短路径,单源点最短路径是指：给定一个出发点（单源点）和一个有向网

50、G=(V,E)，求出源点到其他各顶点之间的最短路径。,例如，对图7-25所示的有向网G，设顶点1为源点，则源点到其余各顶点的最短路径如图7-26所示。,图7-25 有向网G,图7-26 源点1到其余顶点的最短路径,2023/11/14,79,从图7-25可以看出，从顶点1到顶点5有四条路径：15，145，1435，1235，路径长度分别为100，90，60，70，因此，从源点1到顶点5的最短路径为60。,那么怎样求出单源点的最短路径呢？我们可以将源点到终点的所有路径都列出来，然后在里面选最短的一条即可。但是这样做，用手工方式可以，当路径特别多时，就显得特别麻烦，并且没有什么规律，不能用计算机算