《数据结构（C++版）（第二版）》课件第07章.ppt

1、2023年11月28日1第第7章章 图图本章学习内容 7.1 图的基本概念7.2 图的存储结构7.3 图的遍历7.4 生成树和最小生成树7.5 最短路径7.6 有向无环图及其应用2023年11月28日27.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=,。d

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

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

4、度为di，则有e=。21niid1例如，对图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。4 3 1 2 4 3 1 2 4 1 2 （a）图G （b）图G的两个子图 图7-2 图与子图示例2023年11月28日65权在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另

5、一个顶点的距离、耗费等，带权图一般称为网。带权图的示例具体见图7-3。5 3 1 2 4 4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 （a）无向网 （b）有向网 图7-3 无向带权图和有向带权图2023年11月28日76连通图和强连通图在无向图中，若从顶点i到顶点j有路径，则称顶点i到顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。连通图和非连通图示例见图7-4。312412345（a）连通图（b）非连通图 图7-4 连通图和非连通图2023年11月28日8在有向图中，若从顶点i到顶点j有路径，则称从顶点i到顶点j是连通的，若图中任意两个顶

6、点都是连通的，则称此有向图为强连通图，否则称为非强连通图。强连通图和非强连通图示例见图7-5。ABDC12 6543（a）强连通图（b）非强连通图 图7-5 强连通图和非强连通图2023年11月28日97连通分量和强连通分量无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。对于图7-4中的非连通图，它的连通分量见图7-6。12354 图7-6 图7-4（b）的连通分量 2023年11月28日10有向图中，极大的强连通子图为该图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。对于图7-5

7、中的非强连通图，它的强连通分量见图7-7。635214 图7-7 图7-5（b）的强连通分量2023年11月28日118路径、回路在无向图G中，若存在一个顶点序列Vp，Vi1，Vi2，Vin，Vq,使得(Vp,Vi1)，(Vi1,Vi2)，(Vin,Vq)均属于E(G)，则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。9有根图在一个有向图中，若从顶点V有路径可以到达图中的其他所有顶点，则称此有向图为有根图，顶点V称做图的根。10生成

8、树、生成森林连通图的生成树是一个极小连通子图，它包含图中全部n个顶点和n-1条不构成回路的边。非连通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量，则生成森林中有n-m条边。2023年11月28日127.2 图的存储结构图的存储结构 由于图是一种多对多的非线性关系，因此，无法用数据元素在存储区中的物理位置来表示元素之间的关系，故不能用顺序存储结构。下面将介绍常用的三种存储结构：邻接矩阵、邻接表和邻接多重表。7.2.1 邻接矩阵1图的邻接矩阵表示在邻接矩阵表示中，除了存放顶点本身的信息外，还用一个矩阵表示各个顶点之间的关系。若(i,j)E(G)或i,jE(G)，则矩阵中第i行 第j

9、列元素值为1，否则为0。图的邻接矩阵定义为：1 若(i,j)E(G)或i,jE(G)Aij=0 其他情形2023年11月28日13例如，对图7-8所示的无向图和有向图，它们的邻接矩阵见图7-9。12433 1 2 0111101011011010 001100110（a）无向图G3 （b）有向图G4 图7-8 无向图G3及有向图G4（a）G3的邻接矩阵 （b）G4的邻接矩阵 图7-9 邻接矩阵表示2023年11月28日142从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的；（2）第i行或第i 列1的个数为顶点i的度；（3）矩阵中1的个数的一半为图中边的数目；（4）很容易判断顶点i和顶点j之

10、间是否有边相连（看矩阵中i行j列值是否为1）。3从有向图的邻接矩阵可以得出如下结论（1）矩阵不一定是对称的；（2）第i 行中1的个数为顶点i的出度；（3）第j列中1的个数为顶点j的入度；（4）矩阵中1的个数为图中弧的数目；（5）很容易判断顶点i 和顶点j 是否有弧相连。2023年11月28日154网的邻接矩阵表示类似地可以定义网的邻接矩阵为：wij 若(i,j)E(G)或i,jE(G)Aij=0若i=j 其他情形网及网的邻接矩阵见图7-10。074937028420198063160 5 3 1 2 4 3 6 1 2 4 8 9 7 （a）网G5 （b）网G5的邻接矩阵示意图 图7-10 网

11、及邻接矩阵示意图2023年11月28日165图的邻接矩阵数据类型描述图的邻接矩阵数据类型描述如下:const int n=maxn；/图中顶点数 const int e=maxe；/图中边数class graph public:elemtype vn+1;/存放顶点信息v1,v2,vn，不使用v0存储空间int arcsn+1n+1/邻接矩阵 /成员函数说明及定义;2023年11月28日176建立无向图的邻接矩阵void graph:creatadj(graph&g)int i,j,k;for(k=1;kg.vk;/输入顶点信息 for(i=1;i=n;i+)for(j=1;j=n;j+)g.

12、arcsij=0;/矩阵的初值为0for(k=1;kij;/输入一条边(i,j)g.arcsij=1;g.arcsji=1;该算法的时间复杂度为O(n2)。2023年11月28日187建立有向图的邻接矩阵void graph:creatadj(graph&g)int i,j,k;for(k=1;kg.vk;/输入顶点信息 for(i=1;i=n;i+)for(j=1;j=n;j+)g.arcsij=0;for(k=1;kij;/输入一条弧 g.arcsij=1;该算法的时间复杂度为O(n2)。2023年11月28日198建立无向网的邻接矩阵void graph:creatadj(graph&g

13、)int i,j,k;float w;for(k=1;kg.vk;/输入顶点信息 for(i=1;i=n;i+)for(j=1;j=n;j+)if(i=j)g.arcsij=0;else g.arcsij=;/代表顶点i和顶点j无边，上机时可以用一个很大的数代替for(k=1;kijw;/输入一条边(i,j)及权值w g.arcsij=w;g.arcsji=w;该算法的时间复杂度为O(n2)。2023年11月28日209建立有向网的邻接矩阵void graph:creatadj(graph&g)int i,j,k;float w;for(k=1;kg.vk;/输入顶点信息 for(i=1;i=

14、n;i+)for(j=1;j=n;j+)if(i=j)g.arcsij=0;else g.arcsij=;for(k=1;kijw;/输入一条弧 及权值w g.arcsij=w;该算法的时间复杂度为O(n2)。2023年11月28日21若要将得到的邻接矩阵输出，可以使用如下的语句段：for(int i=1;i=n;i+)for(int j=1;j=n;j+)coutg.arcsij ;coutendl;7.2.2 邻接表1图的邻接表表示 将每个结点的边用一个单链表链接起来，若干个结点可以得到若干个单链表，每个单链表都有一个头结点，为将所有头结点联系起来组成一个整体，所有头结点可看成一个一维数组

15、，称这样的链表为邻接表。2023年11月28日22例如，图7-8所示的无向图G3和有向图G4的邻接表如图7-11所示。1 2 3 4 2 4 1 3 4 2 4 1 2 3 （a）无向图G3的邻接表 1 2 3 2 3 3 1 1 2 3 3 2 1 1 （b）有向图G4的邻接表（c）有向图G4的逆邻接表 图7-11 邻接表示例 2023年11月28日232从无向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。3从有向图的邻接表可以得到如下结论（1）第i个链表中结点数目为顶点i的出度；（2）所有链表

16、中结点数目为图中弧数；（3）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在图7-11（c）中已经给出，从该图中可知。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。2023年11月28日244图的邻接表数据类型描述图的邻接表数据类型描述如下：const int n=maxn；/maxn表示图中最大顶点数const int e=maxe；/maxe表示图中最大边数class link /定义链表类型 public:elemtype data;link *next;cla

17、ss node /定义邻接表的表头类型 public:link an+1;void creatlink(node&g);/其他成员函数的说明及定义;在本章中，为描述问题方便直观，我们将elemtype 类型设定为int类型，以此代表图中顶点的序号。2023年11月28日255无向图的邻接表建立void node:creatlink(node&g)int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 g.ai.data=i;g.ai.next=NULL;for(k=1;kij;/输入一条边(i,j)s=new link;/申请一个动态存储单元s-data=j;s-

18、next=g.ai.next;/头插法建立链表g.ai.next=s;s=new link;s-data=i;s-next=g.aj.next;g.aj.next=s;该算法的时间复杂度为O(n+e)。2023年11月28日266有向图的邻接表建立void node:creatlink(node&g)int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 g.ai.data=i;g.ai.next=NULL;for(k=1;kij;/输入一条边(i,j)s=new link;/申请一个动态存储单元s-data=j;s-next=g.ai.next;g.ai.nex

19、t=s;该算法的时间复杂度为O(n+e)。2023年11月28日277网的邻接表的数据类型描述网的邻接表的数据类型可描述如下：const int n=maxn；/maxn表示网中最大顶点数const int e=maxe；/maxe表示网中最大边数class link /定义链表类型 public:elemtype data;float w;/定义网上的权值类型为浮点型 link *next;class node /定义邻接表的表头类型 public:link an+1;void creatlink(node&g);2023年11月28日288无向网的邻接表建立void node:creatl

20、ink(node&g)float w;int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 g.ai.data=i;g.ai.w=0;g.ai.next=NULL;for(k=1;kijw;/输入一条边(i,j)及该边上的权值s=new link;/申请一个动态存储单元sdata=j;s-w=w;s-next=g.ai.next;g.ai.next=s;s=new link;s-data=i;s-w=w;s-next=g.aj.next;g.aj.next=s;该算法的时间复杂度为O(n+e)。2023年11月28日299有向网的邻接表建立void node:c

21、reatlink(node&g)float w;int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 g.ai.data=i;g.ai.next=NULL;for(k=1;kijw;/输入一条边(i,j)及该边上的权值s=new link;/申请一个动态存储单元sdata=j;s-w=w;s-next=g.ai.next;g.ai.next=s;该算法的时间复杂度为O(n+e)。2023年11月28日30另外，请注意上面的算法中，建立的邻接表不是惟一的，与你从键盘输入边的顺序有关，输入边的顺序不同，得到的链表也不同。若要将得到的邻接表输出，可以使用如下的语句：f

22、or(int i=1;i=n;i+)link*p=g.ai.next;couti;while(p-next!=NULL)coutdata;p=p-next;coutdataendl;2023年11月28日317.2.3 邻接多重表在无向图的邻接表中，每条边(Vi,Vj)由两个结点表示，一个结点在第i个链表中，另一个结点在第j个链表中，当需要对边进行操作时，就需要找到表示同一条边的两个结点，这给操作带来不便，在这种情况下采用邻接多重表比较方便。在邻接多重表中，每条边用一个结点表示，每个结点由五个域组成，其结点结构为：Mark i next1 j next2 其中Mark为标志域，用来标记这条边是

23、否被访问过，i和j域为一条边的两个顶点，next1 和next2为两个指针域，分别指向依附于i顶点的下一条边和j顶点的下一条边。而表头与邻接表的表头类似。2023年11月28日32邻接多重表的形式见图7-12。1 3 4 2 1 2 3 4 2 4 1 3 1 2 （a）无向图G6 （b）G6的邻接多重表 图7-12 邻接多重表示例2023年11月28日337.3 图的遍历图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图中所有的顶点，但是，在图中有回路，从图中某一顶点出发访问图中其他顶点

24、时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到，因此，图的遍历较树的遍历更复杂。我们可以设置一个全局型标志数组visited来标志某个顶点是否被访过，未访问的值为false，访问过的值为true。根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索遍历和广度优先搜索遍历。2023年11月28日347.3.1 深度优先搜索遍历1深度优先搜索思想深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点i作为遍历的初始点，则深度优先搜索遍历可定义如下：（1）首先访问顶点i，并将其访问标记置为访问过，即visitedi=true；（2）然后搜索与顶

25、点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visitedj=true，然后从j开始重复此过程，若j已访问，再看与i有边相连的其他顶点；（3）若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才的过程，直到图中所有顶点都被访问完为止。2023年11月28日35例如，对图7-13所示的无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出其中三种，其他可作类似分析写出来。3 1 2 4 5 7 6 8 图7-13 无向图G7在无向图G7中，从顶点1出发的深度优先搜索遍历序列（列举三种）为：1,2,4,8,5,6,3,71,2,5,8,

26、4,7,3,61,3,6,8,7,4,2,52023年11月28日362连通图的深度优先搜索若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不惟一的。但是若我们给定图的存储结构，则从某一顶点出发的遍历结果应是惟一的。（1）用邻接矩阵实现图的深度优先搜索以图7-13中无向图G7为例，来说明算法的实现，G7的邻接矩阵见图7-14。0111100010000100100001001000001010000010011000010001100100000110 图7-14 无向图G7的邻接矩

27、阵2023年11月28日37算法描述如下：#include#define elemtype intconst int n=8;/图中顶点数 const int e=10;/图中边数bool visitedn+1;class graph public:elemtype vn+1;/存放顶点信息v1,v2,vn，不使用v0存储空间int arcsn+1n+1;/邻接矩阵void creatadj(graph&g);/建立邻接矩阵void dfs(graph g,int i);/实现深度优先搜索遍历;2023年11月28日38void graph:creatadj(graph&g)/建立邻接矩阵 i

28、nt i,j,k;for (k=1;kg.vk;/输入顶点信息 for(i=1;i=n;i+)for(j=1;j=n;j+)g.arcsij=0;for(k=1;kij;/输入一条边(i,j)g.arcsij=1;g.arcsji=1;2023年11月28日39void 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)&(!visitedj)dfs(g,j);void main()grap

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

30、深度优先搜索仍以图7-13中无向图G7为例，来说明算法的实现，G7的邻接表见图7-16 1 2 3 4 5 6 7 8 2 3 1 4 1 6 2 8 2 8 3 8 3 8 4 5 6 7 2 3 7 5 图7-16 G7的邻接表2023年11月28日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月28日43class n

31、ode /定义邻接表的表头类型 public:link an+1;void creatlink(node&g);/建立邻接表void dfs1(node g,int i);/实现深度优先搜索遍历;void node:creatlink(node&g)int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 g.ai.data=i;g.ai.next=NULL;2023年11月28日44for(k=1;kij;/输入一条边(i,j)s=new link;/申请一个动态存储单元s-data=j;s-next=g.ai.next;g.ai.next=s;s=new lin

32、k;s-data=i;s-next=g.aj.next;g.aj.next=s;2023年11月28日45void 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月28日46用刚才的算法及图7-16，可以描述从顶点7出发的深度优先搜索遍历示意图，见图7-17，其中实线表示下一层递归，虚线表示递归返回，箭头旁边的数字表示调用的步骤。D F S

33、 1(7)D F S 1(3)D F S 1(1)D F S 1(2)D F S 1(4)D F S 1(8)D F S 1(5)D F S 1(6)211 41 31 2111 03456987图7-17 邻接表深度优先搜索示意图于是，从顶点7出发的深度优先搜索遍历序列，从图7-17中可得出为7，3，1，2，4，8，5，6。从其他顶点出发的深度优先搜索序列，请读者自已写出。2023年11月28日473非连通图的深度优先搜索若图是非连通图或非强连通图，则从图中某一个顶点出发，不能用深度优先搜索访问到图中所有顶点，而只能访问到一个连通子图（即连通分量）或只能访问到一个强连通子图（即强连通分量）。

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

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

36、8这对于连通图是可以办到的，但若是非连通图，则只须对每个连通分量都选一顶点作开始点，都进行广度优先搜索，则可以得到非连通图的遍历。2023年11月28日502连通图的广度优先搜索（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存储空间

37、int arcsn+1n+1;/邻接矩阵void creatadj(graph&g);/建立邻接矩阵void bfs(graph g,int i);/实现图的广度优先搜索遍历;2023年11月28日51void graph:creatadj(graph&g)int i,j,k;for (k=1;kg.vk;/输入顶点信息 for(i=1;i=n;i+)for(j=1;j=n;j+)g.arcsij=0;for(k=1;kij;/输入一条边(i,j)g.arcsij=1;g.arcsji=1;2023年11月28日52void graph:bfs(graph g,int i)/从顶点i出发实现图

38、的广度优先搜索遍历 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(g.arcsij=1)&(!visitedj)coutg.vj ;visitedj=true;r+;qr=j;void main()graph g;g.creatadj(g);for(i=1;i=n;i+)visitedi=false;g.bfs(g,1);/从顶点1出

39、发实现图的广度优先搜索遍历2023年11月28日53（2）用邻接表实现图的广度优先搜索遍历仍以无向图G7及图7-16所示的邻接表来说明邻接表上实现广度优先搜索遍历的过程。具体算法描述如下：#include#define elemtype intconst int n=8;/maxn表示图中最大顶点数const int e=10;/maxe表示图中最大边数bool visitedn+1;class link /定义链表类型 public:elemtype data;link *next;class node /定义邻接表的表头类型 public:link an+1;void creatlink(

40、node&g);/建立邻接表void bfs1(node g,int i);/实现图的广度优先搜索遍历;2023年11月28日54void node:creatlink(node&g)int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 g.ai.data=i;g.ai.next=NULL;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年1

41、1月28日55void node:bfs1(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月28日56void main()node g;g.creatlink(g);for(i=1;i=n;i+)visitedi=false;g.bfs1(g,1);/从顶点1出发实现图的广度优先搜索遍历根据该算法及图7-16，可以得到

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

43、到整个非连通图或非强连通图的广度优先搜索遍历序列。遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的广度优先搜索遍历算法即可。具体可以表示如下：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月28日587.4 生成树和最小生成树生成树和最小生成树7.4.1 基本概念1生成树在图论中，常常将树定义为一个无回路连通图。例如，图7-18中的两个图就是无回路的连通图。乍一看它似乎不是树，但只要选定某个顶点做根并以树根为起点对每条边定向

44、，就可以将它们变为通常的树。3 1 2 4 5 1 2 4 3 5 图7-18 两个无回路的连通图2023年11月28日59在一个连通图中，有n个顶点，若存在这样一个子图，含有n个顶点，n-1条不构成回路的边，则这个子图称为生成树，或者定义为：一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图为图G的生成树。由于n个顶点的连通图至少有n-1条边，而所有包含n-1条边及n个顶点的连通图都是无回路的树，所以生成树是连通图中的极小连通子图。所谓极小是指边数最少。若在生成树中去掉任何一条边，都会使之变为非连通图；若在生成树上任意增加一条边，就会构成回路。那么，对给定的连通图，如何求得它的生成树

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

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

47、搜索遍历或连通图的广度优先搜索遍历算法得到。2023年11月28日622生成森林若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，得到的不是生成树，而是生成森林。且若非连通图有n 个顶点、m个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算法得到。3最小生成树在一般情况下，图中的每条边若给定了权值，这时，我们所关心的不是生成树，而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树。下面将介绍求最小

48、生成树的两种方法：普里姆算法和克鲁斯卡尔算法。2023年11月28日637.4.2 普里姆（prim）算法1普里姆算法思想下面仅讨论无向网的最小生成树问题。普里姆算法的思想是：在图中任取一个顶点k作为开始点，令集合U=k，集合W=V-U，其中V为图中所有顶点集合，然后找出：一个顶点在集合U中，另一个顶点在集合W中的所有的边中，权值最短的一条边，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶点的距离，使之保持最小，再重复此过程，直到W为空集为止。求解过程参见下面的图7-20各步骤。2023年11月28日64 6 4 1

49、 2 4 3 6 2 1 3 5 7 6 5 5 5 1 2 3 4 5 6 6 5 1 （a）无向网 （b）u=1 w=2,3,4,5,6 3 1 2 4 5 6 1 4 5 5 5 3 1 2 4 5 6 4 2 1 5 5 （c）u=1,3 w=2,4,5,6 （d）u=1,3,6 w=2,4,52023年11月28日65 3 1 2 4 5 6 4 2 1 5 5 1 2 4 3 5 6 4 2 1 5 3（e）u=1,3,6,4 w=2,5 （f）u=1,3,6,4,2 w=55 4 2 1 3 1 2 4 3 5 6（g）u=1,3,6,4,2,5 w=图7-20 prim算法构造

50、最小生成树的过程2023年11月28日662普里姆算法实现普里姆算法的算法实现，可描述如下（假设网用邻接矩阵作存储结构，与图的邻接矩阵类似，只是将0变为，1变为对应边上权值，而矩阵中对角线上的元素值为0，本算法参照的示例为图7-20（a）中的无向网）：#include const int n=6;/定义网中顶点数const int e=10;/定义网中边数 class edgeset /定义一条生成树的边 public:int fromvex;/边的起点 int endvex;/边的终点 int weight;/边上的权值;2023年11月28日67class tree public:int