1、第7章 图 数据结构（C+描述）目录7.6拓扑排序7.1 图的基本概念图的基本概念7.2 图的存贮结构7.3 图的遍历图的遍历7.4 生成树和最小生成树生成树和最小生成树7.5最短路径最短路径退出7.1 图的基本概念图的基本概念7.1.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,
2、3,E2=,。d A cA b a 2 1 3(a)无向图 G1 (b)有向图 G2 图 7-1 无向图和有向图 7.1.2 图的基本术语 1.有向图和无向图有向图和无向图在图中，若用箭头标明了边是有方向性的，则称这样的图为有向图，否则称为无向图。如图7-1中，G1为无向图，G2为有向图。在无向图中，一条边（x,y）与（y,x）表示的结果相同，用圆括号表示，在有向图中，一条边与表示的结果不相同，故用尖括号表示。x,y表示从顶点x发向顶点y的边，x为始点，y为终点。有向边也称为弧，x为弧尾，y为弧头,则x,y表示为一条弧,而y,x表示y为弧尾，x为弧头的另一条弧。2.完全图、稠密图、稀疏图 具有
3、n个顶点，n(n-1)/2条边的图，称为完全无向图，具有n个顶点，n(n-1)条弧的有向图,称为完全有向图。完全无向图和完全有向图都称为完全图。对于一般无向图，顶点数为n，边数为e，则 0e n(n-1)/2。对于一般有向图，顶点数为n，弧数为e，则 0en(n-1)。当一个图接近完全图时，则称它为稠密图，相反地，当一个图中含有较少的边或弧时，则称它为稀疏图。3.度、入度、出度在图中，一个顶点依附的边或弧的数目，称为该顶点的度。在有向图中，一个顶点依附的弧头数目，称为该顶点的入度。一个顶点依附的弧尾数目，称为该顶点的出度，某个顶点的入度和出度之和称为该顶点的度。另外，若图中有n个顶点，e条边或
4、弧，第i个顶点的度为di，则有e=21niid14.子图子图若有两个图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 图与子图示意 4 3 1 2 5 权 在图的边或弧中给出相关的数，称为权。权可以代表一个顶点到另一个顶点的距离，耗费等，带权图一般称为网。带权图的示例具体见图7-3。(a)无向网 (b)有向网 图 7-3 无向带权图和有向带权图 5 3 1 2 4
5、4 1 6 7 2 3 5 8 A B C 2 1 5 3 4 6 连通图和强连通图连通图和强连通图在无向图中，若从顶点i到顶点j有路径，则称顶点i和顶点j是连通的。若任意两个顶点都是连通的，则称此无向图为连通图，否则称为非连通图。连通图和非连通图示例见图7-4。3 1 2 4 1 2 3 4 5（a）连通图 (b)非连通图 图 7-4 连通图和非连通图 在有向图中，若从顶点i到顶点j有路径，则称从顶点i和顶点j是连通的，若图中任意两个顶点都是连通的，则称此有向图为强连通图，否则称为非强连通图。强连通图和非强连通图示例见图7-5。A B D C 1 2 6 5 4 3(a)强连通图 (b)非强
6、连通图 图 7-5 强连通图和非强连通图 7 连通分量和强连通分量 无向图中，极大的连通子图为该图的连通分量。显然，任何连通图的连通分量只有一个，即它本身，而非连通图有多个连通分量。对于图7-4 中的非连通图，它的连通分量见图7-6。1 2 3 5 4 图 7-6 图 7-4(b)的连通分量 有向图中，极大的强连通子图为该 图的强连通分量。显然，任何强连通图的强连通分量只有一个，即它本身，而非强连通图有多个强连通分量。对于图7-5 中的非强连通图，它的强连通分量见图7-7。6 3 5 图 7-7 图 7-5(b)的强连通分量 2 1 4 8路径、回路 在无向图G中，若存在一个顶点序列Vp,Vi
7、1，Vi2，Vin，Vq,使得（Vp,Vi1）,(Vi1,Vi2),.，(Vin,Vq)均属于E（G），则称顶点Vp到Vq存在一条路径。若一条路径上除起点和终点可以相同外，其余顶点均不相同，则称此路径为简单路径。起点和终点相同的路径称为回路，简单路径组成的回路称为简单回路。路径上经过的边的数目称为该路径的路径长度。9 有根图 在一个有向图中，若从顶点V有路径可以到达图中的其它所有顶点，则称此有向图为有根图，顶点V称作图的根。10 生成树、生成森林 连通图的生成树是一个极小连通子图，它包含图中全部n个顶点和n-1条不构成回路的边。非边通图的生成树则组成一个生成森林。若图中有n个顶点，m个连通分量
8、，则生成森林中有n-m条边。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 其它情形 例如,对图7-8所示的无向图和有向图,它们的邻接矩阵见图7-9。3 1 2(a)无向图 G3 (b)有向图 G4 图 7-8 无向图 G3 及有向图 G4 1 2 4 3 0111101011011010 001100110 (a)G3 的邻接
9、矩阵 (b)G4 的邻接矩 图 7-9 邻接矩阵表示 2 从无向图的邻接矩阵可以得出如下结论（1）矩阵是对称的;（2）第i行或第i 列1的个数为顶点i 的度;（3）矩阵中1的个数的一半为图中边的数目;（4）很容易判断顶点i 和顶点j之间是否有边相连(看矩阵中i行j列值是否为1)。3 从有向图的邻接矩阵可以得出如下结论从有向图的邻接矩阵可以得出如下结论（1）矩阵不一定是对称的;（2）第i 行中1的个数为顶点i 的出度;（3）第i列中1的个数为顶点 i的入度;（4）矩阵中1的个数为图中弧的数目;（5）很容易判断顶点i 和顶点j 是否有弧相连.4 网的邻接矩阵表示 类似地可以定义网的邻接矩阵为：wi
10、j 若（i,j）E(G)或i,jE(G)Aij=0 若i=j 其它情形网及网的邻接矩阵见图7-10。7493728421986316 (a)网 G5 (b)网 G5 的邻接矩阵示意图 图 7-10 网及邻接矩阵示意图 5 3 1 2 4 3 6 1 2 4 8 9 7 5 图的邻接矩阵数据类型描述图的邻接矩阵数据类型描述图的邻接矩阵数据类型描述如下:const int n=maxn；/图中顶点数 const int e=maxe；/图中边数struct graph elemtype Vn+1;/存放顶点信息v1,v2,.vn，不使用v0存储空间int arcsn+1n+1 /邻接矩阵;6 建立
11、无向图的邻接矩阵 void 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;该算法的时间复杂度为O（n2）。7.建立有向图的邻接矩阵 void 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.arcs
12、ij=1;该算法的时间复杂度为O（n2）。8.建立无向网的邻接矩阵void creatadj(graph&g)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=;for(k=1;kijw;/输入一条边(i,j)及权值w g.arcsij=w;g.arcsji=w;该算法的时间复杂度为O（n2）。9.建立有向网的邻接矩阵void creatadj(graph&g)int i,j,k;float w;for (k=1;kg.vk;/输入顶点信息
13、 for(i=1;i=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）。7.2.2 邻接表邻接表1 图的邻接表表示图的邻接表表示 将每个结点的边用一个单链表链接起来，若干个结点可以得到若干个单链表，每个单链表都有一个头结点，所有头结点组成一个一维数组，称这样的链表为邻接表。例如，图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
14、2 3 3 1 1 2 3 3 1 1 3 (b)有向图 G4 的邻接表 (c)有向图 G4 的逆邻接表 图 7-11 邻接表示例 12432 从无向图的邻接表可以得到如下结论（1）第i 个链表中结点数目为顶点i的度；（2）所有链表中结点数目的一半为图中边数；（3）占用的存储单元数目为n+2e。3 从有向图的邻接表可以得到如下结论从有向图的邻接表可以得到如下结论（1）第i 个链表中结点数目为顶点i的出度；（2）所有链表中结点数目为图中弧数；（3）占用的存储单元数目为n+e。从有向图的邻接表可知，不能求出顶点的入度。为此，我们必须另外建立有向图的逆邻接表，以便求出每一个顶点的入度。逆邻接表在图7
15、-11(c)中已经给出，从该图中可知。有向图的逆邻接表与邻接表类似，只是它是从入度考虑结点，而不是从出度考虑结点。4 图的邻接表数据类型描述图的邻接表数据类型描述图的邻接表数据类型描述如下：const int n=maxn；/maxn表示图中最大顶点数const int e=maxe；/maxe图中最大边数struct link /定义链表类型 elemtype data;link *next;struct node /定义邻接表的表头类型 elemtype v;/顶点信息link *next;an+1;5.无向图的邻接表建立void creatlink()int i,j,k;link *s;
16、for(i=1;i=n;i+)/建立邻接表头结点 ai.v=i;ai.next=NULL;for(k=1;kij;/输入一条边(i,j)s=new link;/申请一个动态存储单元sdata=j;s-next=ai.next;ai.next=s;s=new link;s-data=i;s-next=aj.next;aj.next=s;该算法的时间复杂度为O（n+e）。6.有向图的邻接表建立 void creatlink()int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 ai.v=i;ai.next=NULL;for(k=1;kij;/输入一条边 s=new
17、 link;/申请一个动态存储单元sdata=j;s-next=ai.next;ai.next=s;该算法的时间复杂度为O（n+e）。7.网的邻接表的数据类型描述 网的邻接表的数据类型可描述如下：const int n=maxn；/maxn表示网中最大顶点数const int e=maxe；/maxe网中最大边数struct link /定义链表类型 elemtype data;float w;/定义网上的权值类型为浮点型 link *next;struct node /定义邻接表的表头类型 elemtype v;/顶点信息link *next;an+1;8 无向网的邻接表建立 void cr
18、eatlink()float w;int i,j,k;link *s;for(i=1;i=n;i+)/建立邻接表头结点 ai.v=i;ai.next=NULL;for(k=1;kijw;/输入一条边(i,j)及该边上的权值s=new link;/申请一个动态存储单元sdata=j;s-w=w;s-next=ai.next;ai.next=s;s=new link;s-data=i;s-w=w;s-next=aj.next;aj.next=s;该算法的时间复杂度为O（n+e）。9 有向网的邻接表建立 void creatlink()float w;int i,j,k;link *s;for(i=
19、1;i=n;i+)/建立邻接表头结点 ai.v=i;ai.next=NULL;for(k=1;kijw;/输入一条弧 及该弧上的权值s=new link;/申请一个动态存储单元sdata=j;s-w=w;s-next=ai.next;ai.next=s;该算法的时间复杂度为O（n+e）。另外，请注意上面的算法中，建立的邻接表不是唯一的,与你从键盘输入边的顺序有关，输入的边的顺序不同，则得到的链表也不同。7.2.3 邻接多重表 在无向图的邻接表中，每条边（Vi,Vj）由两个结点表示，一个结点在第i个链表中，另一个结点在第j个链表中，当需要对边进行操作时，就需要找到表示同一条边的两个结点，这给操作
20、带来不便，在这种情况下采用邻接多重表较方便。在邻接多重表中，每条边用一个结点表示，每个结点由五个域组成，其结点结构为：Mark i next1 j next2 其中mark为标志域，用来标记这条边是否被访问过，i和j域为一条边的两个顶点，next1 和next2为两个指针域，分别指向依附于i顶点的下一条边和j顶点的下一条边。而表头与邻接表的表头类似。邻接多重表的形式见图7-12。1 3 4 2(a)无向图 G6 （b）G6 的邻接多重表 图 7-12 邻接多重表示例 1 2 3 4 2 4 1 3 1 2 7.3 图的遍历图的遍历和树的遍历类似，图的遍历也是从某个顶点出发，沿着某条搜索路径对图
21、中所有顶点各作一次访问。若给定的图是连通图，则从图中任一顶点出发顺着边可以访问到该图中所有的顶点，但是，在图中有回路，从图中某一顶点出发访问图中其它顶点时，可能又会回到出发点，而图中可能还剩余有顶点没有访问到，因此，图的遍历较树的遍历更复杂。我们可以设置一个全局型标志数组visited来标志某个顶点是否被访过，未访问的值为0，访问过的值为1。根据搜索路径的方向不同，图的遍历有两种方法：深度优先搜索遍历和广度优先搜索遍历。7.3.1深度优先搜索遍历深度优先搜索遍历1 深度优先搜索思想深度优先搜索思想 深度优先搜索遍历类似于树的先序遍历。假定给定图G的初态是所有顶点均未被访问过，在G中任选一个顶点
22、i作为遍历的初始点，则深度优先搜索遍历可定义如下：(1)首先访问顶点i，并将其访问标记置为访问过，即visitedi=1；(2)然后搜索与顶点i有边相连的下一个顶点j，若j未被访问过，则访问它，并将j的访问标记置为访问过，visitedj=1，然后从j开始重复此过程，若j已访问，再看与i有边相连的其它顶点；(3)若与i有边相连的顶点都被访问过，则退回到前一个访问顶点并重复刚才过程，直到图中所有顶点都被访问完止。例如，对图7-13所示无向图G7，从顶点1出发的深度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似分析。在无向图G7中，从顶点1出发的深度优先搜索遍历序列举三种为：1,2,4,8
23、,5,6,3,71,2,5,8,4,7,3,61,3,6,8,7,4,2,5 3 1 2 4 5 7 6 8 7-13 无向图 G7 2 连通图的深度优先搜索 若图是连通的或强连通的，则从图中某一个顶点出发可以访问到图中所有顶点，否则只能访问到一部分顶点。另外，从刚才写出的遍历结果可以看出，从某一个顶点出发的遍历结果是不唯一的。但是,若我们给定图的存贮结构,则从某一顶点出发的遍历结果应是唯一的。(1)用邻接矩阵实现图的深度优先搜索 以图7-13中无向图G7 为例，来说明算法的实现，G7的邻接矩阵见图7-14。0111100010000100100001001000001010000010011
24、000010001100100000110 图 7-14 无向图 G7 的邻接矩阵 3 1 2 4 5 7 6 8 7-13 无向图 G7 算法描述为下面形式：void dfs(int i)/从顶点i 出发遍历 int j;coutg.vi;/输出访问顶点 visitedi=1;/全局数组访问标记置1表示已经访问 for(j=1;j=n;j+)if(g.arcsi j=1)&(!visitedj)dfs(j);用上述算法和无向图G7，可以描述从顶点1出发的深度优先搜索遍历过程，示意图见图7-15，其中实线表示下一层递归调用，虚线表示递归调用的返回。从图7-15中，可以得到从顶点1的遍历结果为
25、1,2,4,8,5,6,3,7。同样可以分析出从其它顶点出发的遍历结果。DFS(1)DFS(2)DFS(4)DFS(8)DFS(5)DFS(6)DFS(3)DFS(7)图 7-15 邻接矩阵深度优先搜索示意图 (2)用邻接表实现图的深度优先搜索用邻接表实现图的深度优先搜索仍以图7-13中无向图G7 为例，来说明算法的实现，G7的邻接表见图7-16，3 1 2 4 5 7 6 8 7-13 无向图 G7 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 的邻接表 算法描述为下面形式：void dfs1(in
26、t i)link*p;coutdata)dfs1(p-data);p=p-next;用刚才算法及图7-16，可以描述从顶点7出发的深度优先搜索遍历示意图，见图7-17,其中实线表示下一层递归，虚线表示递归返回，箭头旁边数字表示调用的步骤。于是，从顶点7出发的深度优先搜索遍历序列，从图7-17中可得出为 7，3，1，2，4，8，5，6。从其它顶点出发的深度优先搜索序列，请读者自已写出。DFS1(7)DFS1(3)DFS1(1)DFS1(2)DFS1(4)DFS1(8)DFS1(5)DFS1(6)2 1 14 13 12 11 10 3 4 5 6 9 8 7 7-17 邻接表深度优先搜索示意图
27、3非连通图的深度优先搜索 若图是非连通的或非强连通图，则从图中某一个顶点出发。不能用深度优先搜索访问到图中所有顶点，而只能访问到一个连通子图（既连通分量）或只能访问到一个强连通子图（既强连通分量）。这时，可以在每个连通分量或每个强连通分量中都选一个顶点，进行深度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图的遍历结果。遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的深度优先搜索遍历算法即可。具体实现如下：for(int i=1;i=n;i+)if(!visitedi)dfs(i);for(int i=1;i=n;i+)if(!vi
28、sitedi)dfs1(i);或者7.3.2 广度优先搜索遍历广度优先搜索遍历1 广度优先搜索的思想广度优先搜索的思想广度优先搜索遍历类似于树的按层次遍历。设图G的初态是所有顶点均未访问，在G 中任选一顶点i作为初始点，则广度优先搜索的基本思想是：(1)首先访问顶点i，并将其访问标志置为已被访问，即visitedi=1；(2)接着依次访问与顶点i有边相连的所有顶点W1，W2，Wt；(3)然后再按顺序访问与W1，W2，Wt有边相连又未曾访问过的顶点；依此类推，直到图中所有顶点都被访问完为止。例如，对图7-13所示无向图G7，从顶点1出发的广度优先搜索遍历序列可有多种，下面仅给出三种，其它可作类似
29、分析。在无向图G7中，从顶点1出发的广度优先搜索遍历序列举三种为：1,2,3,4,5,6,7,81,3,2,7,6,5,4,81,2,3,5,4,7,6,8 3 1 2 4 5 7 6 8 7-13 无向图 G7 2 连通图的广度优先搜索(1)用邻接矩阵实现图的广度优先搜索遍历用邻接矩阵实现图的广度优先搜索遍历仍以图7-13中无向图G7及7-14所示的邻接矩阵来说明对无向图G7的遍历过程 3 1 2 4 5 7 6 8 7-13 无向图 G7 0111100010000100100001001000001010000010011000010001100100000110 图 7-14 无向图
30、G7 的邻接矩阵 根据该算法用及图7-14中的邻接矩阵，可以得到图7-13的无向图G7 的广度优先搜索序列，若从顶点1 出发，广度优先搜索序列为：1，2，3，4，5，6，7，8。若从顶点3出发，广度优先搜索序列为：3，1，6，7，2，8，4，5,从其它点出发的广度优先搜索序列可根据同样类似方法分析。算法描述如下：void bfs(int i)/从顶点i出发遍历 int Qn+1;/Q为队列 int f,r,j;/f,r分别为队列头，尾指针 f=r=0;/设置空队列 coutg.vi;/输出访问顶点 visitedi=1;/全局数组标记置1表示已经访问 r+;qr=i;/入队列 while(fr
31、)f+;i=qf;/出队列for(j=1;j=n;j+)if(g.arcsij=1)&(!visitedj)coutg.vj;visitedj=1;r+;qr=j;（2）用邻接表实现图的广序优先搜索遍历）用邻接表实现图的广序优先搜索遍历仍以无向图G7及图7-16所示邻接表来说明邻接表上实现广度优先搜索遍历的过程 3 1 2 4 5 7 6 8 7-13 无向图 G7 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 的邻接表 根据该算法及图7-16，可以得到图G7的广度优先搜索序列，若从顶点1出发，广度优
32、先搜索序列为：1，2，3，4，5，6，7，8，若从顶点7出发，广度优先搜索序列为：7，3，8，1，6，4，5，2，从其它顶点出发的广度优先搜索序列可根据同样类似方法分析。算法描述如下：void BFS1(int i)int qn+1;/定义队列 int f,r;link *p;/P为搜索指针 f=r=0;coutai.v;visitedi=1;r+;qr=i;/进队 while(fdata)coutdata.v;visitedp-data=1;r+;qr=p-data;p=p-next;3.非连通图的广度优先搜索 若图是非连通的或非强连通图，则从图中某一个顶点出发。不能用广度优先搜索遍历访问到
33、图中所有顶点，而只能访问到一个连通子图（既连通分量）或只能访问到一个强连通子图（既强连通分量）。这时，可以在每个连通分量或每个强连通分量中都选一个顶点，进行广度优先搜索遍历，最后将每个连通分量或每个强连通分量的遍历结果合起来，则得到整个非连通图或非强连通图的广度优先搜索遍历序列。遍历算法实现与连通图的只有一点不同，即对所有顶点进行循环，反复调用连通图的广度优先搜索遍历算法即可。具体可以表示如下：for(int i=1;i=n;i+)for(int i=1;i=n;i+)if(!visitedi)或 if(!visitedi)bfs(i);bfs1(i);7.4 生成树和最小生成树生成树和最小生
34、成树7.4.1 基本概念基本概念1 生成树生成树在图论中，常常将树定义为一个无回路连通图。例如，图7-18中的两个图就是无回路的连通图。乍一看它似乎不是不是树，但只要选定某个顶点做根并以树根为起点对每条边定向，就可以将它们变为通常的树。3 1 2 4 5 1 2 4 3 5 7-18 两个无回路的连通图 在一个连通图中，有n个顶点，若存在这样一个子图，含有n个顶点，n-1条不构成回路的边，则这个子图称为生成树，或者定义为：一个连通图G的子图如果是一棵包含G的所有顶点的树，则该子图为图G 的生成树。由于n个顶点的连通图至少有n-1条边，而所有包含n-1 条边及n个顶点的连通图都是无回路的树，所以
35、生成树是连通图中的极小连通子图，所谓极小是指边数最少，若在生成树中去掉任何一条边，都会使之变为非连通图，若在生成树上任意增加一条边，就会构成回路。那么，对给定的连通图，如何求得它的生成树呢？回到我们前面提到的图的遍历，访问过图中一个顶点后，要访问下一个顶点，一般要求两个顶点有边相连，即必须经过图中的一条边，要遍历图中n 个顶点且每个顶点都只遍历一次，则必须经过图中的n-1条边，这n-1条边构成连通图的一个极小连通子图，所以它是连通图的生成树，由于遍历结果可能不唯一，所以得到的生成树也是不唯 一的。要求得生成树，可考虑用刚才讲过的深度优先搜索遍历算法及广度优先搜索遍历算法。对于深度优先搜索算法D
36、FS或DFS1，由DFS（i）递归到DFS（j），中间必经过一条边（i,j），因此，只需在DFS(j)调用前输出这条边或保存这条边，即可求得生成树的一条边，整个递归完成后，则可求得生成树的所有边。对于广度优先搜索算法BFS或BFS1，若i 出队，j 入队，则(i,j)为一条树边。因此，可以在算法的if 语句中输出这条边，算法完成后，将会输出n-1条边，也可求得生成树。由深度优先搜索遍历得到的生成树，称为深度优先生成树，由广度优先搜索遍历得到的生成树，称为广度优先生成树。图7-13中无向图G7的两种生成树见 图7-19。若一个图是强连通的有向图，同样可以得到它的生成树。生成树可以利用连通图的深度
37、优先搜索遍历或连通图的广度优先搜索遍历算法得到。1 4 2 5 3 6 8 7 2 7 6 8 3 5 4 1(a)深度优先生成树 (b)广度优先生成树 图 7-19 两种生成树示意图 3 1 2 4 5 7 6 8 7-13 无向图 G7 2生成森林 若一个图是非连通图或非强连通图，但有若干个连通分量或若干个强连通分量，则通过深度优先搜索遍历或广度优先搜索遍历，不可以得到生成树，但可以得到生成森林，且若非连通图有 n 个顶点，m 个连通分量或强连通分量，则可以遍历得到m棵生成树，合起来为生成森林，森林中包含n-m条树边。生成森林可以利用非连通图的深度优先搜索遍历或非连通图的广度优先搜索遍历算
38、法得到。3 最小生成树 在一般情况下，图中的每条边若给定了权，这时，我们所关心的不是生成树，而是生成树中边上权值之和。若生成树中每条边上权值之和达到最小，称为最小生成树。下面将介绍求最小生成树的两种方法：普里姆算法和克鲁斯卡尔算法。7.4.2 普里姆算法 1 普里姆(prim)算法思想 下面仅讨论无向网的最小生成树问题。普里姆方法的思想是：在图中任取一个顶点K作为开始点，令U=k，W=V-U，其中V为图中所有顶点集，然后找一个顶点在U中，另一个顶点在W中的边中最短的一条，找到后，将该边作为最小生成树的树边保存起来，并将该边顶点全部加入U集合中，并从W中删去这些顶点，然后重新调整U中顶点到W中顶
39、点的距离,使之保持最小，再重复此过程，直到W为空集止。求解过程参见图7-20。假设开始顶点就选为顶点1，故首先有U=1，W=2，3，4，5，6 (a)无向网 (b)u=1 w=2,3,4,5,6 6 4 1 2 4 6 3 6 2 1 3 5 7 6 5 5 5 1 2 3 4 5 6 6 5 1 3 1 2 4 6 5 6 1 4 5 5 5 3 1 2 4 6 5 6 4 2 1 5 5(c)u=1,3 w=2,4,5,6 (d)u=1,3,6 w=2,4,5 3 1 2 4 6 5 6 4 2 1 5 5(e)u=1,3,6,4 w=2,5 (f)u=1,3,6,4,2 w=5 1 2
40、4 6 3 5 6 4 2 1 5 3 (g)u=1,3,6,4,2,5 w=5 4 2 1 3 1 2 4 3 5 6 图 7-20 prim 方法构造最小生成树的过程 7.4.3 克鲁斯卡尔（克鲁斯卡尔（kruskal）算法算法1 克鲁斯卡尔算法基本思想克鲁斯卡尔算法基本思想克鲁斯卡尔算法的基本思想是：将图中所有边按权值递增顺序排列，依次选定取权值较小的边，但要求后面选取的边不能与前面选取的边构成回路，若构成回路，则放弃该条边，再去选后面权值较大的边，n个顶点的图中，选够n-1条边即可。例如，对图7-20（a）中无向网，用克鲁斯卡尔算法求最小生成树的过程见图7-22。2 4 5 6 1 3
41、 1 2 5 1 3 1 4 2 6(a)选第 1 条边 (b)选第 2 条边 (c)选第 3 条边 (d)选第 4 条边 2 3 5 1 3 1 4 6 2 6 4 2 1 2 3 5 1 4 6 3 6 1 2 4 6 3 5 6 4 2 1 3 5(e)选第 5 条边(不能选（1,4）边，会构成回路，但可选（2,3）或(5,3)中之一)5 1 2 4 6 3 6 4 2 1 3 5 或者 图 7-22 克鲁斯卡尔方法求最小生成树的过程 7.5最短路径最短路径交通网络中常常提出这样的问题：从甲地到乙地之间是否有公路连通?在有多条通路的情况下，哪一条路最短?交通网络可用带权图来表示。顶点表示
42、城市名称，边表示两个城市有路连通，边上权值可表示两城市之间的距离、交通费或途中所花费的时间等。求两个顶点之间的最短路径，不是指路径上边数之和最少，而是指路径上各边的权值之和最小。另外，若两个顶点之间没有边，则认为两个顶点无通路，但有可能有间接通路(从其它顶点达到)。路径上的开始顶点(出发点)称为源点，路径上的最后一个顶点称为终点，并假定讨论的权值不能为负数。7.5.1单源点最短路径单源点最短路径1 单源点最短路径单源点最短路径单源点最短路径是指：给定一个出发点(单源点)和一个有向网G=(V，E),求出源点到其它各顶点之间的最短路径。那么怎样求出单源点的最短路径呢?我们可以将源点到终点的所有路径
43、都列出来,然后在里面选最短的一条即可。但是这样做,用手工方式可以,当路径特别多时,显得特别麻烦,并且没有什么规律,不能用计算机算法实现。迪杰斯特拉(Dijkstra)在做了大量观察后,首先提出了按路长度递增序产生各顶点的最短路径算法,我们称之为迪杰斯特拉算法。2 迪杰斯特拉算法的基本思想迪杰斯特拉算法的基本思想算法的基本思想是:设置并逐步扩充一个集合S，存放已求出其最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，其中V为网中所有顶点集合。按最短路径长度递增的顺序逐个以V-S中的顶点加到S中，直到S中包含全部顶点，而V-S为空。具体做法是:设源点为Vl,则S中只包含顶点Vl，令W=V-S，
44、则W中包含除Vl外图中所有顶点，Vl对应的距离值为0，W中顶点对应的距离值是这样规定的：若图中有弧则Vj顶点的距离为此弧权值，否则为(一个很大的数)，然后每次从W中的顶点中选一个其距离值为最小的顶点Vm加入到S中，每往S中加入一个顶点Vm，就要对W中的各个顶点的距离值进行一次修改。若加进Vm做中间顶点，使+的值小于值，则用+代替原来Vj的距离，修改后再在W中选距离值最小的顶点加入到S中，如此进行下去，直到S中包含了图中所有顶点为止 迪杰斯特拉算法的求解过程 10 3 5 20 8 25 4 30 3 30 1 2 3 5 4 (a)一个有向网点 (b)源点 1 到其它顶点的初始距离 1 2 3
45、 5 4 12 3 8 25 30 1 2 3 5 4(c)第一次求得的结果 (d)第二次求得的结果 3 8 12 4 1 2 3 5 4 3 8 12 4 3 8 12 4(e)第三次求得的结果 (f)第四次求得的结果 1 2 3 5 4 1 2 3 5 4 图 7-27 迪杰斯特拉算法求最短路径过程及结果 7.5.2所有顶点对之间的最短路径 1 顶点对之间的最短路径概念 所有顶点对之间的最短路径是指：对于给定的有向网G=(V,E),要对G中任意一对顶点有序对V、W(VW),找出V到W的最短距离和W到V的最短距离。解决此问题的一个有效方法是:轮流以每一个顶点为源点,重复执行迪杰斯特拉算法n次
46、,即可求得每一对顶点之间的最短路径,总的时间复杂度为O(n3)。下面将介绍用弗洛伊德(Floyd)算法来实现此功能,时间复杂度仍为O(n3),但该方法比调用n次迪杰斯特拉方法更直观一些。2 弗洛伊德算法的基本思想弗洛伊德算法的基本思想弗洛伊德算法仍然使用前面定义的图的邻接矩阵arcsn+1n+1来存储带权有向图。算法的基本思想是:设置一个nxn的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)ij表示顶点i到顶点j的路径长度，K表示运算步骤。开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为，当K=O时,A(0)ij=arcsij,以后逐步尝试在原路径中
47、加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：第 一 步，让 所有 边 上 加 入 中 间 顶 点 1，取 A i j 与Ai1+A1j中较小的值作Aij的值，完成后得到A(1)，因此，弗洛伊德算法可以描述为:A(0)ij=arcsij;/arcs为图的邻接矩阵 A(k)ij=minA(k-1)ij,A(k-1)ik+A(k-1)kj其中 k=1,2,n第二步，让所有边上加入中间顶点2，取Aij与Ai2+A2j中较小的值，完成后得到A(2)，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果,
48、A(n)ij表示顶点i到顶点j的最短距离。3 弗洛伊德算法实现弗洛伊德算法实现在用弗洛伊德算法求最短路径时,为方便求出中间经过的路径,增设一个辅助二维数组pathn+1n+1，其中pathij是相应路径上顶点j的前一顶点的顶点号。算法描述如下：Void floyd(const int n)for(int i=1;i=n;i+)for(int j=1;j=n;j+)aij=arcsijif(i!=j)&(aij)pathij=i;else pathij=0;for(int k=1;k=n;k+)for i=1;i=n;i+)for(j=1;j=n;j+)if(aik+akjaij)aij=aik
49、+akj;pathij=pathkj;for(i=1;i=n;i+)/输出路径长度及路径for(j=1;j=n;j+)if(i!=j)coutaij“:”;int next=pathij;coutj;while(next!=i)cout“”next;next=pathinext;cout“”iendl;7.6拓扑排序 7.6.1 实现规则实现规则1 基本概念基本概念 通常我们把计划、施工过程、生产流程、程序流程等都当成一个工程，一个大的工程常常被划分成许多较小的子工程，这些子工程称为活动，这些活动完成时，整个工程也就完成了。例如，计算机专业学生的课程开设可看成是一个工程，每一门课程就是工程中的
50、活动，图7-30给出了若干门所开设的课程，其中有些课程的开设有先后关系，有些则没有先后关系，有先后关系的课程必须按先后关系开设，如开设数据结构课程之前必须先学完程序设计基础及离散数学，而开设离散数学则必须先并行学完高等数学、程序设计基础课程。.课程代码 课程名称 先修课程 C1 高等数学 C2 程序设计基础 C3 离散数学 C1,C2 C4 数据结构 C2,C3 C5 高级语言程序设计 C2 C6 编译方法 C5,C4 C7 操作系统 C4,C9 C8 普遍物理 C1 C9 计算机原理 C8 (a)课程开设 (b)课程开设优先关系的有向图 图 7-30 学生课程开设工程图 C8 C6 C5 C
