第13章图 计算机软件技术基础教程 教学课件

《第13章图 计算机软件技术基础教程 教学课件》由会员分享，可在线阅读，更多相关《第13章图 计算机软件技术基础教程 教学课件（130页珍藏版）》请在装配图网上搜索。

1、第13章 图13.1 图的基本概念图的基本概念13.2 图的存储方法图的存储方法13.3 图的遍历图的遍历13.4 生成树和最小生成树生成树和最小生成树13.5 最短路径最短路径13.6 拓扑排序拓扑排序13.7 关键路径关键路径第第13章章 图图返回主目录返回主目录第13章 图第13章 图13.1 图的基本概念图的基本概念 图(G)是一种非线性数据结构，它由两个集合V(G)和E(G)组成，形式上记为G=(V,E),其中V(G)是顶点(Vertex)的非空有限集合，而E(G)是V(G)中任意两个顶点之间的关系集合，又称为边(Edge)的有限集合。当G中的每条边有方向时，则称G为有向图。有向边通

2、常使用由两个顶点组成的有序对来表示，记为：起始顶点，终止顶点。有向边又称为弧，因此弧的起始顶点就称为弧尾，终止顶点称为弧头。例如图13.1(a)给出了一个有向图的示例，该图的顶点集和边集分别为第13章 图第13章 图 V(G1)=A,B,C E(G1)=,若G中的每条边是无方向的，则称G为无向图。这时两个顶点之间最多只存在一条边。无向图用两个顶点组成的无序对表示，记为：(顶点1，顶点2)。图13.1(b)给出了一个无向图的示例。该图的顶点集和边集分别为 V(G2)=A,B,C E(G2)=(A,B),(B,C),(C,A)=(B,A),(C,B),(A,C)在下面的讨论中，我们不考虑顶点到其自

3、身的边，也不允许一条边在图中重复出现，如图13.2所示。在以上两条的约束下，则边和顶点之间存在以下的关系：第13章 图图13.2 本章中不考虑的图例ABC(a)存在顶点到自身的边AB(b)两点间有多条相同的边第13章 图 (1)对一个无向图，它的顶点数n和边数e满足0en(n1)/2的关系。如果e=n(n1)/2，则该无向图称为完全无向图。(2)对一个有向图，它的顶点数n和边数e满足0en(n1)的关系。如果e=n(n1)，则称该有向图为完全有向图。(3)如果e nlgn，则该图为稀疏图，否则为稠密图。如果两个同类型的图G1=(V1,E1)和G2(V2,E2)存在关系V1V2,E1E2,则称G

4、1是G2的子图。图13.3 给出了G1和G2的子图的示例。在无向图G中，若边(vi,vj)E(G)，则称顶点vi和vj相互邻接，两个顶点互为邻接点，并称边(vi,vj)关联于顶点vi和vj或称边(vi,vj)与顶点vi和vj相关联。第13章 图图13.3 子图示例ACB(a)G1的子图ACB(b)G2的子图第13章 图 在无向图中关联于某一顶点vi的边的数目称为vi的度，记为D(vi)。例如图13.1(b)中的顶点A的度为2。在有向图中，把以顶点vi为终点的边的数目称为vi的入度，记为ID(vi)；把以顶点vi为起点的边的数目称为vi的出度，记为OD(vi)；把顶点vi的度定义为该顶点的入度和

5、出度之和。例如图13.1(a)中顶点A的入度为1，出度为2，度为3。如果图G中有n个顶点，e条边，且每个顶点的度为D(vi)(1in)，则存在以下关系：在一个图中，如果图的边或弧具有一个与它相关的数时，这个数就称为该边或弧的权，这个数常用来表示一个顶点到另一个顶点的距离或耗费。如果图中的每条边都具有权时，这个带权图被称为网络，简称为网。图13.4给出了一个网络示例。第13章 图图13.4 网络示例13248653第13章 图 在一个图中，若从顶点v1出发，沿着一些边经过顶点v1,v2,vn-1到达顶点vn，则称顶点序列(v1,v2,vn-1,vn)为从v1到vn的一条路径。例如在图13.1(b

6、)中，(A,B,C)是一条路径。而在图13.1(a)中，(A,C,B)就不是一条路径。将无权图沿路径所经过的边数称为该路径的长度。而对有权图，则取沿路径各边的权之和作为此路径的长度。在图13.4中顶点1到顶点4的路径长度为8。若路径中的顶点不重复出现，则这条路径被称为简单路径。起点和终点相同并且路径长度不小于2的简单路径被称为简单回路或者简单环。例如图13.1(b)的无向图中顶点序列(A,B,C)是一条简单路径，而(A,B,C,A)则是一个简单环。第13章 图 在一个有向图中，若存在一个顶点v，从该顶点有路径可到达图中其他的所有顶点，则称这个有向图为有根图，v称为该图的根。例如图13.1(a)

7、就是一个有根图，该图的根是A和B。在无向图G中，若顶点vi和vj(ij)有路径相通，则称vi和vj是连通的。如果V(G)中的任意两个顶点都连通，则称G是连通图，否则为非连通图。例如图13.1(b)就是一个连通图。无向图G中的极大连通子图称为G的连通分量。对任何连通图而言，连通分量就是其自身，对非连通图可有多个连通分量。图13.5给出了一个无向图和它的两个连通分量。在有向图G中，若从vi到vj(ij)、从vj到vi都存在路径，则称vi和vj是强连通的。第13章 图1234567(a)无向图G12345(b)G的连通分量67图13.5 无向图及其连通分量第13章 图 若有向图V(G)中的任意两个顶

8、点都是强连通的，则称该图为强连通图。有向图中的极大连通子图称作有向图的强连通分量。例如图13.1(a)中的顶点A和B是强连通的，但该有向图不是一个强连通图。第13章 图13.2 图的存储方法图的存储方法 13.2.1 邻接矩阵存储方法邻接矩阵存储方法 在邻接矩阵存储方法中使用一个一维数组来存放图中每个结点的数据信息和使用一个二维数组（又称为邻接矩阵）来表示图中各顶点之间的关系。对一个有n个顶点的图G，将使用一个nn的矩阵来表示其顶点间的关系，矩阵的每一行和每一列都对应一个顶点。矩阵中的元素Ai,j可按以下规则取值：0i,jn1 图13.6(a)和(b)的邻接矩阵分别为A1和A2：第13章 图图

9、13.6 有向图G1和无向图G2示例 1324(a)有向图G1(b)无向图G21324第13章 图0001100000000110A10101100100011110A2 在无向图的邻接矩阵中，行或列中的非零元素个数等于对应的顶点的度数；在有向图中，每行非零元素的个数对应于该顶点的出度，每列非零元素的个数对应于该顶点的入度。对于网络，邻接矩阵元素Ai,j可按以下规则取值：0i,jn1第13章 图图13.4中的网络的邻接矩阵为 当一个图用邻接矩阵表示时，可用以下数据类型来说明：#definen /*图的顶点数*/#define e/*图的边数*/typedef char vextype;/*顶点

10、的数据类型*/typedef floatadjtype;/*顶点权值的数据类型*/0006500000000380A第13章 图typedef struct vextype vexsn;/*顶点数组*/adjtypearcsnn;/*邻接矩阵*/graph;利用上述类型说明可以给一个无向网络邻接矩阵的建立算法:CREATGRAPH(graph g)/*建立无向网络*/int i,j,k;float w;for(i=0;ivexsi=getchar();/*读入顶点信息，建立顶点表*/for(i=0;in;i+)for(j=0;jarcsij=0;/*邻接矩阵初始化*/for(k=0;karcs

11、ij=w;/*写入邻接矩阵*/garcsji=w;第13章 图 /*CREATGRAPH*/如要建立无向图，可在以上算法中改变w的类型，并使输入值为1即可；如要建立有向网络，只需将写入矩阵的两个语句中的后一个语句去除即可。在以上算法中，如果邻接矩阵是一个稀疏矩阵，则存在存储空间浪费现象。该算法的执行时间是O(n+n2+e)。由于通常en2，所以算法的时间复杂度是O(n2)。第13章 图 13.2.2 邻接表存储方法邻接表存储方法 邻接表存储方法是一种顺序存储与链式存储相结合的存储方法。在这种方法中，只考虑非零元素，所以在图中的顶点很多而边很少时，可以节省存储空间。邻接表存储结构由两部分组成：对

12、于每个顶点vi,使用一个具有两个域的结构体数组来存储，这个数组称为顶点表。其中一个域称为顶点域(vertex)，用来存放顶点本身的数据信息；而另一个域称为指针域(link)，用来存放依附于该顶点的边所组成的单链表的表头结点的存储位置。邻接于vi的顶点vj链接成的单链表称为vi的邻接链表。邻接链表中的每个结点由两个域构成：一是邻接点域(adjvex)，用来存放与vi相邻接的顶点vj的序号j(可以是顶点vj在顶点表中所占数组单元的下标)；其二是链域(next)，用来将邻接链表中的结点链接在一起。对于顶点表和邻接链表中的结点可用以下的数据类型来说明：第13章 图typedef char vextyp

13、e;/*定义顶点数据信息类型*/typedef struct node /*邻接链表结点*/int adjvex;/*邻接点域*/struct node next;/*链域*/edgenode;typedef struct vextype vertex;/*顶点域*/edgenode link;/*指针域*/vexnode;vexnode gan;/*顶点表*/第13章 图 对于无向图，vi的邻接链表中每个结点都对应与vi相关联的一条边，所以我们将无向图的邻接链表称为边表。对于有向图，vi的邻接链表中每个结点都对应于以vi为起始点射出的一条边，所以有向图的邻接链表也称为出边表。有向图还有一种逆

14、邻接表表示法，这种方法的vi邻接链表中的每个结点对应于以vi为终点的一条边，这种邻接链表称为入边表。对应于图13.6(a)的邻接表和逆邻接表如图13.7(a)、(b)所示。对应于13.6(b)的邻接表如图13.7(c)所示，其中表示该域为空。无论是无向图还是有向图，其邻接表的建立都比较简单，下面给出无向图邻接表的建立算法：第13章 图 CREATADJLIST(Vexnode ga)/*建立无向图的邻接表*/int i,j,k;edgenode s;for(i=0;in;i+)gai.vertex=getchar();/*读入顶点信息和边表头指针初始化*/gai.link=NULL;for(k

15、=0;kadjvex=j;snext=gai.link;gai.link=s;/*将s插入顶点vi的边表头部*/s=malloc(sizeof(edgenode);/*生成邻接点序号为i的边表结点s*/sadjvex=i;snext=gaj.link;gaj.link=s;/*将s插入顶点vj的边表头部*/*CREATADJLIST */第13章 图 如要建立有向图的邻接表，则只需去除上述算法中生成邻接点序号为i的边表结点s，并将s 插入顶点vj边表头部那一段语句组即可。若要建立网络的邻接表，只要在边表的每个结点中增加一个存储边上的权的数据域即可。该算法的执行时间是O(n+e)。邻接矩阵和邻接

16、表是图中最常用的存储结构，它们各有所长，具体体现在以下几点：(1)一个图的邻接矩阵表示是惟一的，而其邻接表表示不惟一，这是因为邻接链表中的结点的链接次序取决于建立邻接表的算法和边的输入次序。(2)在邻接矩阵表示中判定(vi,vj)或vi,vj是否是图中的一条边，只需判定矩阵中的第i行第j列的元素是否为零即可。第13章 图 而在邻接表中，则需要扫描vi对应的邻接链表，最坏的情况下需要的执行时间为O(n)。(3)求图中边的数目时，使用邻接矩阵必须检测完整个矩阵之后才能确定，所消耗的时间为O(n2)；而在邻接表中只需对每个边表中的结点个数计数便可确定。当en2时，使用邻接表计算边的数目，可以节省计算

17、时间。在具体应用中选择哪种存储方法，主要是考虑算法本身的特点和空间的存储密度来确定。第13章 图13.3 图图 的的 遍遍 历历 13.3.1 深度优先搜索遍历深度优先搜索遍历 图的深度优先搜索遍历类似于树的先序遍历，是树的先序遍历的推广。在假设初始状态是图中所有顶点都未被访问的前提下，这种方法从图中某一顶点vi出发，访问此顶点，并进行标记，然后依次搜索vi的每个邻接点vj；若vj未被访问过，则对vj进行访问和标记，然后依次搜索vj的每个邻接点;若vj的邻接点未被访问过，则访问vj的邻接点，并进行标记，直到图中和vi有路径相通的顶点都被访问。若图中尚有顶点未被访问过（非连通的情况下），则另选图

18、中的一个未被访问的顶点作为出发点，重复上述过程，直到图中所有顶点都被访问为止。第13章 图 这种方法在访问了顶点vi后，访问vi的一个邻接点vj；访问vj之后，又访问vj的一个邻接点，依次类推，尽可能向纵深方向搜索，所以称为深度优先搜索遍历。显然这种搜索方法具有递归的性质。图13.8给出了一个深度优先搜索遍历的示例，其中虚线表示一种搜索路线。相应的顶点访问序列为A,B,C,E,D。当选择邻接矩阵作为图的存储结构时，深度优先搜索遍历算法如下：Int visitedn;/*定义visited为全局变量，n为顶点数 graph g;/*g为全局变量*/第13章 图第13章 图DFSA(int i)/

19、*从vi出发深度优先搜索图g，g用邻接矩阵表示*/int j;printf(node:%cn,g.vexsi);/*访问出发点vi*/visitedi=1;/*标记vi已被访问*/for(j=0;jadjvex=0)DFSL(padjvex);/*从vi的未曾被访问过的邻接点出发进行深度优先搜索遍历*/p=pnext;/*DFSL */第13章 图 当图13.8采用13.9的邻接表来表示时，按以上算法进行遍历得到的序列为A,B,C,E,D。因为搜索n个顶点的所有邻接点需要对边表各结点扫描一遍，而边表结点的数目为2e，所以算法的时间复杂度为O(2e+n)，空间复杂度为O(n)。在使用邻接表作为存

20、储结构时，由于图的邻接表表示不惟一，所以DFSL算法得到的DFS序列也不惟一，它取决于邻接表中边表结点的链接次序。第13章 图图13.9 邻接表的一种表示ABCD101043E0124第13章 图 13.3.2 广度优先搜索遍历广度优先搜索遍历 图的广度优先搜索遍历类似于树的按层次遍历。在假设初始状态是图中所有顶点都未被访问的条件下，这种方法从图中某一顶点vi出发，先访问vi，然后访问vi的邻接点vj。在所有的vj都被访问之后，再访问vj的邻接点vk，依次类推，直到图中所有和初始出发点vi有路径相通的顶点都被访问为止。若图是非连通的，则选择一个未曾被访问的顶点作为起始点，重复以上过程，直到图中

21、所有顶点都被访问为止。在这种方法的遍历过程中，先被访问的顶点，其邻接点也先被访问，具有先进先出的特性，所以可以使用一个队列来保存已访问过的顶点，以确定对访问过的顶点的邻接点的访问次序。为了避免重复访问一个顶点，也使用了一个辅助数组visitedn来标记顶点的访问情况。下面分别给出以邻接矩阵和邻接表为存储结构时的广度优先搜索遍历算法BFSA和BFSL：第13章 图BFSA(int k)/*从vk出发广度优先搜索遍历图g，g用邻接矩阵表示*/inti,j;SETNULL(Q);/*Q置为空队*/printf(%cn,g.vexsk);/*访问出发点vk*/visitedk=1;/*标记vk已被访问

22、*/ENQUEUE(Q,k);/*访问过的顶点序号入队*/while(!EMPTY(Q)/*队非空时执行下列操作*/i=DEQUEUE(Q);/*队头元素序号出队*/第13章 图for(j=0;jadjvex!=1)/*vi的邻接点未曾被访问*/printf(%cn,gapadjvex.vertex);visitedpadjvex=1;ENQUEUE(Q,padjvex);/*访问过的顶点入队*/p=pnext;/*BFSL */第13章 图 对于有n个顶点和e条边的连通图，BFSA算法的while循环和 for循环都需执行n次，所以BFSA算法的时间复杂度为O(n2)，同时BFSA算法使用了

23、一个长度均为n的队列和辅助标志数组，所以空间复杂度为O(n)；BFSL算法的外while循环要执行n次，而内while循环执行次数总计是边表结点的总个数2e，所以BFSL算法的时间复杂度为O(n+2e)；同时BFSL算法也使用了一个长度均为n的队列和辅助标志数组，所以空间复杂度为O(n)。对一个图，按广度优先搜索遍历先后顺序得到的顶点序列称为该图的广度优先搜索遍历序列，简称为BFS序列。一个图的BFS序列也不是惟一的，它与算法、图的存储结构和初始出发点有关。但当确定了有多个邻接点时，按邻接点的序号从小到大进行选择和指定初始出发点后，以邻接矩阵作为存储结构得到的BFS序列是惟一的，而以邻接表作为

24、存储结构得到的BFS序列并不惟一，它取决于邻接表中边表结点的链接次序。第13章 图 假设顶点A,B,C,D,E对应的标识数组元素为visited0，,visited4，使用BFSA算法对图13.8从顶点A开始的广度优先搜索遍历过程如下：(1)调用BFSA(0)，访问顶点A，并将visited0置1;然后将顶点A的序号0入队，第一个出队的顶点序号是0，搜索到A的三个邻接点B,D,E,对它们进行访问并将序号1,3,4入队。(2)第二个出队的顶点序号是1，搜索到B的三个邻接点A,E,C,对未进行访问过的顶点C进行访问并将其序号2入队。(3)第三个出队的顶点序号是3，搜索到D的一个邻接点A，因已访问过

25、，故无序号入队。(4)第四个出队的顶点序号是4，搜索到E的两个邻接点A和B，因已访问过，故无顶点序号入队。第13章 图 (5)第五个出队的顶点序号是2，搜索到C的一个邻接点B，因已访问过，故无顶点序号入队。又因为此时队列中已无顶点序号，队列为空，所以搜索过程结束。搜索遍历得到的BFS序列是A,B,D,E,C。使用BFSL算法，对图13.9从顶点A开始的广度优先搜索遍历过程如下：(1)调用BFSL(0)，访问顶点A，将visited0置1，然后将顶点A的序号0入队，第一个出队的顶点序号是0，搜索到A的邻接点B,E,D,对它们进行访问，并将序号1,4,3入队。(2)第二个出队的顶点序号是1，搜索到

26、B的邻接点A,C,E，对未访问过的邻接点C进行访问，并将序号2入队。第13章 图 (3)第三个出队的顶点序号是4，搜索到E的两个邻接点A和B，因都已访问过，故无顶点序号入队。(4)第四个出队的顶点序号是3，搜索到D的邻接点A，因已访问过，故无顶点序号入队。(5)第五个出队的顶点序号是2，搜索到C的邻接点B，因已 访问过，故无顶点序号入队。又因为此时队列中已无顶点序号，队列为空，所以搜索过程结束。搜索遍历得到的BFS序列是A,B,E,D,C。第13章 图13.4 生成树和最小生成树生成树和最小生成树 在图论中，树是指一个无回路存在的连通图。一个连通图G的生成树指的是一个包含了G的所有顶点的树。对

27、于一个有n个顶点的连通图G，其生成树包含了n1条边，从而生成树是G的一个极小连通的子图。所谓极小是指该子图具有连通所需的最小边数，若去掉一条边，该子图就变成了非连通图；若任意增加一条边，该子图就有回路产生。当给定一个无向连通图G后，如何找出它的生成树呢?可以从G的任意顶点出发，作一次深度优先搜索或广度优先搜索来访问G中的n个顶点，并将顺次访问的两个顶点之间的路径记录下来。这样G中的n个顶点和从初始点出发顺次访问余下的n1个顶点所经过的n1条边就构成了G的极小连通子图，也就是G的一棵生成树。第13章 图 通常我们将深度优先搜索得到的生成树称为深度优先搜索生成树，简称为DFS生成树，而将广度优先搜

28、索得到的生成树称为广度优先搜索生成树，简称为BFS生成树。对于前面所给的DFSA和BFSA算法，只需在if语句中的DFSA调用语句前或if语句中加入将(vi,vj)打印出来的语句，即可构成相应的生成树算法。连通图的生成树不是惟一的，它取决于遍历方法和遍历的起始顶点。在遍历方法确定之后，从不同的顶点出发进行遍历，可以得到不同的生成树。对于非连通图可通过多次调用由DFSA或BFSA构成的生成树算法来求出非连通图中各连通分量对应的生成树，这些生成树构成了非连通图的生成森林。使用DFSA构成的生成树算法和BFSA构成的生成树算法对图13.8从顶点A开始进行遍历得到的生成树如图13.10所示。第13章

29、图图13.10 生成树的示例ADBEC(a)DFS生成树ADBEC(b)BFS生成树第13章 图 当对一个连通网络构造生成树时，可以得到一个带权的生成树。我们把生成树各边的权值总和作为生成树的权，而具有最小权值的生成树构成了连通网络的最小生成树。最小生成树的构造是有实际应用价值的。例如要在n个城市之间建立通信网络，而不同城市之间建立通信线路需要一定的花费，则构造最小生成树，将对应于使用最少的经费来建立相应的通信网络。也就是说，构造最小生成树，就是在给定n个顶点所对应的权矩阵（代价矩阵）的条件下，给出代价最小的生成树。构造最小生成树的算法有多种，其中大多数算法都利用了最小生成树的一个性质（简称M

30、ST性质）。MST性质指出：假设G=(V,E)是一个连通网络，U是V中的一个真子集，若存在顶点uU和顶点vVU的边(u,v)是一条具有最小权的边，则必存在G的一棵最小生成树包括这条边(u,v)。第13章 图图13.11 含有(u,v)的回路uuvvUV-U第13章 图 MST性质可用反证法加以证明：假设G中的任何一棵最小生成树T都不包含(u,v)，其中uU 和vVU。由于T是最小生成树，所以必然有一条边(u,v)（其中uU 和vVU）连接两个顶点集U和VU。当(u,v)加入到T中时，T中必然存在一条包含了(u,v)的回路，如图13.11所示。如果在T中保留(u,v),去掉(u,v),则得到另一

31、棵生成树T。因为(u,v)的权小于(u,v)的权，故T的权小于T的权，这与假设矛盾，因此MTS性质得证。下面介绍构造最小生成树的两种常用算法：Prim(普里姆)算法和Kruskal(克鲁斯卡尔)算法。1Prim算法算法第13章 图 设G(V,E)是有n个顶点的连通网络，T=(U,TE)是要构造的生成树，初始时U=，TE=。首先从V中取出一个顶点u0放入生成树的顶点集U中作为第一个顶点，此时T=(u0,)；然后从uU，vVU的边(u,v)中找一条代价最小的边(u*,v*)，将其放入TE中并将v*放入U中，此时T=(u0,v*,(u0,v*)；继续从uU，vVU的边(u,v)中找一条代价最小的边(

32、u*,v*)，将其放入TE中并将v*放入U中，直到U=V为止。这时T的TE中必有n1条边，构成所要构造的最小生成树。显然，Prim算法的关键是如何找到连接U和VU的最短边（代价最小边）来扩充T。设当前生成树T中已有k个顶点，则U和VU中可能存在的边数最多为k(nk)条，在如此多的边中寻找一条代价最小的边是困难的。第13章 图 注意到在相邻的寻找最小代价的边的过程中，有些操作具有重复性，所以可通过将前一次寻找所得到的最小边存储起来，然后与新找到的边进行比较，如果新找到的边比原来已找到的边短，则用新找到的边代替原有的边，否则保持不变。为此设立以下的边的存储结构：typedef struct int

33、fromvex,endvex;/*边的起点和终点*/float length;/*边的权值*/edge;edgeTn1;float distnn;/*连通网络的带权邻接矩阵*/第13章 图这样便可给出Prim算法描述:Prim(int i)/*i给出选取的第一个顶点的下标,最终结果保存在Tn-1数组中*/int j,k,m,v,min,max=100000;float d;edge e;v=i;/*将选定顶点送入中间变量v*/for(j=0;j=v)Tj.endvex=j+1;Tj.length=distvj+1;else Tj.endvex=j;Tj.length=distvj;for(k=

34、0;kn1;k+)/*求第k条边*/min=max;for(j=k;jn1;j+)/*找出最短的边并将最短边的下标记录在m中*/if(Tj.lengthmin)min=Tj.length;m=j;第13章 图e=Tm;Tm=Tk;Tk=e;/*将最短的边交换到Tk单元*/v=Tk.endvex;/*v中存放新找到的最短边在VU中的顶点*/for(j=k+1;jn1;j+)/*修改所存储的最小边集*/d=distvTj.endvex;if(dTj.length);Tj.length=d;Tj.fromvex=v;/*Prim*/第13章 图 以上算法中构造第一个顶点所需的时间是O(n)，求k条边

35、的时间大约为 2-n0k2-nkj2-n0k2-nkj2-n1kjO(1)2)O(1)O(1)(其中O(1)表示某一正常数C，所以上述公式的时间复杂度是O(n2)。下面结合图13.12所示的例子来观察以上算法的工作过程。设选定的第一个顶点为2。第13章 图图13.12 一个网络及其邻接矩阵1019 21105611566618 1419183321 1114 3301013425181911213314656第13章 图 首先将顶点值2写入Ti.fromvex，并将其余顶点值写入相应的Ti.endvex，然后从dist矩阵中取出第2行写入相应的Ti.length中，得到图13.13(a)；在图

36、13.13(a)中找出具有最小权值的边(2,1)，将其交换到下标值为0的单元中，然后从dist矩阵中取出第1行的权值与相应的Ti.length作比较，若取出的权值小于相应的Ti.length，则进行替换，否则保持不变。这里由于边(2,0)和(2,5)的权值大于边(1,0)和(1,5)的权值，进行相应的替换可得到图13.3(b)；在图13.3(b)中找出具有最小权值的边(2,3)，将其交换到下标值为1的单元中，然后从dist矩阵中取出第3行的权值与相应的Ti.length作比较，可见边(3,4)的权值小于边(2,4)的权值，故进行相应的替换可得到13.3(c)；在图13.3(c)中找出具有最小权

37、值的边(1,0)，因其已在下标为2的单元中，故交换后仍然保持不变，然后从dist矩阵中取出第0行的权值与相应的Ti.Length作比较，第13章 图 可见边(0,4)和(0,5)的权值大于边(3,4)和(1,5)的权值，故不进行替换，得到图13.3(d)；在图13.3(d)中找出具有最小权值的边(1,5)，将其交换到下标值为3的单元中，然后从dist矩阵中取出第5行的权值与相应的Ti.length作比较；因边(5,4)的权值大于边(3,4)的权值，故不替换，得到图13.3(e)。至此，整个算法结束，即得出了如图13.3(f)所示的最小生成树。2Kruskal算法算法 Kruskal算法是从另一

38、条途径来求网络的的最小生成树。设G=(V,E)是一个有n个顶点的连通图，则令最小生成树的初值状态为只有n个顶点而无任何边的非连通图T=(V,)，此时图中每个顶点自成一个连通分量。按照权值递增的顺序依次选择E中的边，若该边依附于T中两个不同的连通分量，则将此边加入TE中，否则舍去此边而选择下一条代价最小的边，直到T中所有顶点都在同一连通分量上为止。这时的T，便是G的一棵最小生成树。第13章 图 对于图13.12所示的网络，按Kruskal算法构造最小生成树的过程如图13.14所示。在图13.14(c)中选择最短边(2,3)时，也可选择边(1,3)，这样所构造出的最小生成树是不同的，即最小生成树的

39、形式不惟一，但权值的总和是相同的。在选择了最短边(2,3)之后，在图13.14(d)中首先选择边(1,3)，因其顶点在同一个分量上，故舍去这条边而选择下一条代价最小的边。在图13.14(f)中也是首先选择边(3,5)，但因顶点3和5在同一个分量上，故舍去此边而选择下一条代价最小边(3,4)。第13章 图图13.13 T数组变化情况及最小生成树 下 标 0 1 2 3 4 fromvex 2 2 2 2 2 endvex 0 1 3 4 5 length (5)6 下 标 0 1 2 3 4 fromvex 2 1 2 2 1 endvex 1 0 3 4 5 length 5 10 (6)11

40、(a)初始化后的T数组 (b)找出最短边(2,1)调整后的T数组 下 标 0 1 2 3 4 fromvex 2 2 1 3 1 endvex 1 3 0 4 5 length 5 6 (10)18 11 下 标 0 1 2 3 4 fromvex 2 2 1 3 1 endvex 1 3 0 4 5 length 5 6 10 18 (11)(c)找出最短边(2,3)并调整后 (d)找出最短边(1,0)并调整后第13章 图 下 标 0 1 2 3 4 fromvex 2 2 1 1 3 endvex 1 3 0 5 4 length 5 6 10 11 18 01013425181156(e

41、)找出最短边(1,5)并调整后 (f)最小生成树图13.13 T数组变化情况及最小生成树第13章 图图13.14 Kruskal算法构造最小生成树的过程013425(a)初始状态0134255(b)找到最短边(1,2)0134256(c)找到最短边(2,3)01013425181156(f)找到最短边(3,4)010134251156(e)找到最短边(1,5)0101342556(d)找到最短边(0,1)5第13章 图 在Kruskal算法中，每次都要选择所有边中的最短的边，若用邻接矩阵实现时，则每找一条最短的边就需要对整个邻接矩阵扫描一遍，这样整个算法复杂度太高，而使用邻接表时，由于每条边都

42、被连接两次，这也使寻找最短边的计算时间加倍，所以我们采用以下的存储结构来对图中的边进行表示：typedef structint fromvex,endvex;/*边的起点和终点*/float length;/*边的权值*/int sign;/*该边是否已选择过的标志信息*/edge;第13章 图edge Te /*e为图中的边数*/int Gn;/*判断该边的两个顶点是不是在同一个分量上的数组，n为顶点数*/在Kruskal算法中，如何判定所选择的边是否在同一个分量上，是整个算法的关键和难点。为此我们设置一个G数组，利用G数组的每一个单元中存放一个顶点信息的特性，通过判断两个顶点对应单元的信息

43、是否相同来判定所选择的边是否在同一个分量上。具体算法如下：Kruskal(int n,int e)/*n表示图中的顶点数目，e表示图中的边数目*/int i,j,k,l,min;tfor(i=0;i=n1;i+)/*数组G置初值*/Gi=i;第13章 图for(i=0;i=e1;i+)/*输入边信息*/scanf(%d%d%f,&Ti.fromvex，&Ti.endvex,&Ti.length);Ti.sign=0;j=0;while(jn1)min=1000;for(i=0;i=e1;i+)/*寻找最短边*/if(Ti.sign=0)第13章 图if(Ti.lengthmin)k=Ti.fr

44、omvex;l=Ti.endvex;Ti.sigh=1;if(Gk=Gl)Ti.sign=2;/*在同一分量上舍去*/else j+;for(t=0;tn;t+)/*将最短边的两个顶点并入同一分量*/if(Gt=l)Gt=k;/*Kruskal*/第13章 图13.5 最最 短短 路路 径径 13.5.1 从某个源点到其余各顶点的最短路径从某个源点到其余各顶点的最短路径 迪杰斯特拉(Dijkstra)通过对大量的图中某个源点到其余顶点的最短路径的顶点构成集合和路径长度之间关系的研究发现：若按长度递增的次序来产生源点到其余顶点的最短路径，则当前正要生成的最短路径除终点外，其余顶点的最短路径已生成

45、，即设A为源点，U为已求得的最短路径的终点的集合(初态时为空集)，则下一条长度较长的最短路径(设它的终点为X)或者是弧(A,X)或者是中间只经过U集合中的顶点，最后到达X的路径。例如在图13.15中，要生成从F点到其他顶点的最短路径。首先应找到最短的路径FB，然后找到最短的路径FBC。这里除终点C以外，其余顶点的最短路径FB已生成。第13章 图图13.15 有向网络G和F到其他顶点的最短距离BFBACDE51018674121582425F9FBCFBCAFDFE5122125无路径第13章 图 迪杰斯特拉提出的按路径长度递增次序来产生源点到各顶点的最短路径的算法思想是：对有n个顶点的有向连通

46、网络G=(V,E)，首先从V中取出源点u0放入最短路径顶点集合U中，这时的最短路径网络S=(u0,);然后从uU和vVU中找一条代价最小的边(u*,v*)加入到S中去，此时S=(u0,v*,(u0,v*)。每往U中增加一个顶点，则要对VU中的各顶点的权值进行一次修正。若加进v*作为中间顶点，使得从u0到其他属于VU的顶点vi的路径不加v*时最短，则修改u0到vi的权值，即以(u0,v*)的权值加上(v*,vi)的权值来代替原(u0,vi)的权值，否则不修改u0到vi的权值。接着再从权值修正后的VU中选择最短的边加入S中，如此反复，直到U=V为止。第13章 图 对图13.15中的有向网络按以上算

47、法思想处理，所求得的从源点F到其余顶点的最短路径的过程如图13.16所示。其中单圆圈表示U中的顶点，而双圆圈表示VU中的顶点。连接U中两个顶点的有向边用实线表示，连接U和VU中两个顶点的有向边用虚线表示。圆圈旁的数字为源点到该顶点当前的距离值。初始时，S中只有一个源点F，它到VU中各顶点的路径如图13.16(a)所示；选择图13.16(a)中最小代价边(F,B)，同时由于路径(F,A)大于(F,B,A)和(F,C)大于(F,B,C)，进行相应调整可得到图13.16(b)；选择图13.16(b)中的最小代价边(B,C)，同时由于(F,B,A)大于(F,B,C,A)，进行相应调整可得到图13.16

48、(c)；选择图13.16(c)中最小代价边(C,A)即可得到图13.16(d)；选择图13.16(d)中最小代价边(F,D)即可得到图13.16(e);最后选择(F,E)即可得到图13.16(f)。第13章 图图13.16 Dijkstra算法求最短路径示例BACDE55252425F240(a)选择F作为源点BACDE552525F12230(b)将B加入U187BACDE55252125F1290(c)将C加入U7BACDE55252125F1290(d)将A加入U7BACDE55252125F1290(e)将D加入U7BACDE55252125F1290(f)将E加入U7第13章 图 在

49、计算机上实现此算法时，需要设置一个用于存放源点到其他顶点的最短距离数组Dn，以便于从其中找出最短路径;因为我们不仅希望得到最短路径长度，而且也希望能给出最短路径具体经过那些顶点的信息，所以设置一个路径数组pn，其中pi表示从源点到达顶点i时，顶点i的前趋顶点；为了防止对已经生成的最短路径进行重复操作，使用一个标识数组sn来记录最短路径生成情况，若si=1表示源点到顶点i的最短路径已产生，而si=0表示最短路径还未产生。当顶点A,B,C,D,E,F对应标号0,1,2,3，4,5时，具体算法描述如下：floatDn;int pn,sn;Dijkstra(int v,float dist)/*求源点

50、v到其余顶点的最短路径及长度，第13章 图 int i,j,k,v1,min,max=10000,pre;/*Max中的值用以表示dist矩阵中的值*/v1=v;for(i=0;in;i+)/*各数组进行初始化*/Di=distv1i;if(Di!=Max)pi=v1+1;else pi=0;si=0;第13章 图sv1=1;/*将源点送U*/for(i=0;imax,以保证值为的顶点也能加入U*/for(j=0;jn-1;j+)if(!sj)&(Djmin)/*找出到源点具有最短距离的边*/min=Dj;k=j;sk=1;/*将找到的顶点k送入U*/第13章 图for(j=0;jDk+dis

51、tkj)/*调整VU中各顶点的距离值*/Dj=Dk+distkj;pj=k+1;/*k是j的前趋*/*所有顶点已扩充到U中*/for(i=0;in;i+)printf(%f%d,Di,i)pre=pi;第13章 图while(pre!=0)&(pre!=v+1)printf(%d,pre-1);pre=ppre-1;printf(%d,v);/*Dijkstra*/第13章 图 对图13.14中的有向网络G，以F点为源点，执行上述算法时,D、p、s数组的变化状况如表13.1所示。打印输出的结果为 21 0 2 1 5 5 1 5 12 2 1 5 25 3 5 Max 4 5 0 5 5 Di

52、jkstra算法的时间复杂度为O(n2)，占用的辅助空间是O(n)。第13章 图第13章 图 13.5.2 每一对顶点之间的最短路径每一对顶点之间的最短路径 求一个有n个顶点的有向网络G=(V,E)中的每一对顶点之间的最短路径，可以依次把有向网络的每个顶点作为源点，重复执行n次Dijkstra算法，从而得到每对顶点之间的最短路径。这种方法的时间复杂度为O(n3)。弗洛伊德(Floyd)于1962年提出了解决这一问题的另一种算法。它形式比较简单，易于理解，而时间复杂度同样为O(n3)。Floyd算法是根据给定有向网络的邻接矩阵distnn来求顶点vi到顶点vj的最短路径。这一算法的基本思想是：假

53、设vi和vj之间存在一条路径，但这并不一定是最短路径，试着在vi和vj之间增加一个中间顶点vk。第13章 图 若增加vk后的路径(vi,vk,vj)比(vi,vj)短，则以新的路径代替原路径，并且修改distij的值为新路径的权值；若增加vk后的路径比(vi,vj)更长，则维持distij不变。然后在修改后的dist矩阵中，另选一个顶点作为中间顶点，重复以上的操作，直到除vi和vj顶点的其余顶点都做过中间顶点为止。当我们对初始的邻接矩阵distnn，依次以顶点v1,v2,vn为中间顶点实施以上操作时，将递推地产生出一个矩阵序列dist(k)nn(k=0,1,2,n)。这里初始邻接矩阵distn

54、n被看作dist(0)nn，它给出每一对顶点之间的直接路径的权值;dist(k)nn(1kn)给出了中间顶点的序号不大于k的最短路径长度，而dist(n)nn给出了每一对顶点之间的最短路径长度。为了给出每一对顶点之间最短路径所经过的具体路径，可用一个path矩阵来记录具体路径。path(0)给出了每一对顶点之间的直接路径，而path(n)给出了每一对顶点之间的最短路径，path矩阵中每个元素pathij所保存的值是顶点vi到顶点vj时vj的前趋顶点。第13章 图 为了在算法中始终保持初始邻接矩阵distnn中的元素值不变，可设置一个Ann 矩阵来保存每步所求得的所有顶点对之间的当前最短路径长度

55、。这样可给出以下算法：intpathnn;/*路径矩阵*/Floyd(float A n,dist n)/*A是路径长度矩阵,dist是有向网络G的带权邻接矩阵*/int i,j,k,next,max=10000;第13章 图for(i=0;in;i+)/*设置A和path的初值*/for(j=0;jn;j+)if(distij!=Max)pathij=i+1;/*i是j的前趋*/else pathij=0;Aij=distij;for(k=0;kn;k+)/*以0,1,n-1为中间顶点做n次*/for(i=0;in;i+)for(j=0;j(Aik+Akj)Aij=Aik+Akj;/*修改路

56、径长度*/pathij=pathkj;/*修改路径*/for(i=0;in;i+)/*输出所有顶点对i,j之间最短路径的长度和路径*/for(j=0;jn;j+)printf(%f%d,Aij,j);pre=pathij;while(pre!=0)&(pre!=i+1)第13章 图 printf(%d,pre1);pre=pathipre1;printf(%dn,i);/*Floyd */对图13.14中的有向网络G执行以上算法，矩阵A和path的变化状况如表13.2所示。由于A(4)=A(5)=A(6)和path(4)=path(5)=path(6)，所以表中省略了A(5),A(6)和pat

57、h(5),path(6)，打印输出的结果为第13章 图0 006 1013 210830max 4016510 2535max 45055第13章 图13.6 拓拓 扑扑 排排 序序 无论一项工程的进行、一个产品的生产或一个专业的课程学习，都是由许多按一定次序进行的活动来构成的。这些活动可以是一个工程中的子工程、一个产品生产中的部件生产或课程学习中的一门课程。这些按一定顺序进行的活动，可以使用顶点表示活动、顶点之间的有向边表示活动间的先后关系的有向图来表示，这种有向图称为顶点表示活动网络(Activity On Vertex network，简称AOV网)。AOV网中的顶点也可带有权值，表示一

58、项活动完成所需要的时间。AOV网中的有向边表示了活动之间的制约关系。第13章 图 例如，计算机软件专业的学生必须学完一系列的课程才能毕业，其中一些课程是基础课，无须先修其他课程便可学习；而另一些课程则必须学完其他的基础先修课后才能进行学习。这些课程和课程之间的关系如表13.3所示。它们也可以用图13.17的AOV网表示，这里有向边Ci,Cj表示了课程Ci是课程Cj的先修课程。当限制各个活动只能串行进行时，如果可以将AOV网中的所有顶点排列成一个线性序列vi1,vi2,vin，并且这个序列同时满足关系：若在AOV网中从顶点vi到顶点vj存在一条路径，则在线性序列中vi必在vj之前，我们就称这个线

59、性序列为拓扑序列。把对AOV网构造拓扑序列的操作称为拓扑排序。第13章 图图13.17 表示课程先后关系的AOV网C1C4C2C3C5C7C8C10C12C9C11C6第13章 图 AOV网的拓扑排序序列给出了各个活动按序完成的一种可行方案，但并非任何AOV网的顶点都可排成拓扑序列。当AOV网中存在有向环时，就无法得到该网的拓扑序列。在实际的意义上，AOV网中存在的有向环就意味着某些活动是以自己为先决条件，这显然是荒谬的。例如对于程序的数据流图而言，AOV网中存在环就意味着程序存在一个死循环。任何一个无环的AOV网中的所有顶点都可排列在一个拓扑序列里，拓扑排序的基本操作如表13.3所示。(1)

60、从网中选择一个入度为0的顶点并且输出它。(2)从网中删除此顶点及所有由它发出的边。第13章 图第13章 图 (3)重复上述两步，直到网中再没有入度为0的顶点为止。以上的操作会产生两种结果：一种是网中的全部顶点都被输出，整个拓扑排序完成；另一种是网中顶点未被全部输出，剩余的顶点的入度均不为0，则说明网中存在有向环。用以上操作对图13.17的AOV网拓扑排序的过程如图13.18所示。这里得到了一种拓扑序列C1,C2,C3,C4,C5,C7,C9,C10,C12,C11,C6,C8。从构造拓扑序列的过程中可以看出，在许多的情况下，入度为0的顶点不止一个，这样就可以给出多种拓扑序列。若按所给出的拓扑序

61、列的顺序进行课程学习，都可保证在学习任一门课程时，这门课程的先修课程已经学过。第13章 图图13.18 AOV网拓扑排序过程C4C3C5C7C8C10C12C9C11C6(a)输出C1后C2C4C3C5C7C8C10C12C9C11C6(b)输出C2后C8C10C12C9C11C6(c)输出C3,C4,C5,C7后C8C6(d)输出C9,C10,C12,C11后(e)输出C6,C8后第13章 图 拓扑排序可在有向图的不同存储结构表示方法上实现。下面针对图13.19(a)所给出的AOV网进行讨论。在邻接矩阵中，由于某个顶点的入度由这个顶点相对应的列上的1的个数所确定，而它的出度由顶点所对应的行上

62、的1的个数所确定，所以在这种存储结构上实现拓扑排序算法的步骤是：(1)取1作为第1个新序号。(2)找一个没有得到新序号的全零矩阵列，若没有则停止寻找。这时如果矩阵中所有列都得到了新序号，则拓扑排序完成，否则说明该有向图中有环存在。(3)把新序号赋给找到的列，并将该列对应的顶点输出。第13章 图 (4)将找到的列所对应的行全部置零。(5)新序号增1，重复执行步骤(2)(5)。根据以上步骤，使用一个长度为n的数组来存放新序号时，可给出以下的具体算法：TOPOSORTA(graph g，int n)/*对有n个顶点的有向图，使用邻接矩阵求拓扑排序*/int i,j,k,t,v,Dn=0;v=1;/*

63、新序号变量置1*/for(k=0;kn;k+)第13章 图for(j=0;jn;j+)/*寻找全零列*/if(Dj=0)t=1;for(i=0;iarcsij=1)t=0;break;/*若第j列上有1，则跳出循环*/if(t=1)m=j;break;/*找到第j列为全0列*/if(j!=n)Dm=v;/*将新序号赋给找到的列*/printf(%dt,gvexsm);/*将排序结果输出*/第13章 图 for(i=0;iarcsmi=0;/*将找到的列的相应行置全0*/v+;/*新序号增1*/else break;if(v1n)printf(n The network has a cycle

64、n);/*TOPOSORTA*/第13章 图 对图13.19中G1的邻接矩阵应用以上算法得到的拓扑排序序列为：v1,v2,v4,v3,v5,v6,v7。利用邻接矩阵进行拓扑排序时，程序虽然简单，但效率不高，算法的时间复杂度约为O(n3)。而利用邻接表会使寻找入度为0的顶点的操作简化，从而提高拓扑排序算法的效率。在邻接表存储结构中，为了便于检查每个顶点的入度，可在顶点表中增加一个入度域(id)，这样的邻接表如图13.19(b)所示，这样只需对由n个元素构成的顶点表进行检查就能找出入度为0的顶点。为了避免对每个入度为0的顶点重复访问，可用一个链栈来存储所有入度为0的顶点。在进行拓扑排序前，只要对顶

65、点表进行一次扫描，便可将所有入度为0的顶点都入栈，以后每次从栈顶取出入度为0的顶点，并将其输出。第13章 图 一旦排序过程中出现新的入度为0的顶点，同样又将其入栈。在入度为0的顶点出栈后，根据顶点的序号找到相应的顶点和以该顶点为起点的出边，再根据出边上的邻接点域的值使相应顶点的入度值减1，便完成了删除所找到的入度为0的顶点的出边的功能。在邻接表存储结构中实现拓扑排序算法的步骤为：(1)扫描顶点表，将入度为0的顶点入栈。(2)当栈非空时执行以下操作：将栈顶顶点vi的序号弹出，并输出之；检查vi的出边表，将每条出边表邻接点域所对应的顶点的入度域值减1，若该顶点入度为0，则将其入栈；第13章 图 (

66、3)若输出的顶点数小于n，则输出“有回路”，否则拓扑排序正常结束。在具体实现时，链栈无须占用额外空间，只需利用顶点表中入度域值为0的入度域来存放链栈的指针（即指向下一个存放链栈指针的单元的下标），并用一个栈顶指针top指向该链栈的顶部即可。由此给出以下的具体算法：typedef int datetype;typedef int vextype;typedef struct node第13章 图int adjvex;/*邻接点域*/struct node next;/*链域*/edgenode;/*边表结点*/typedef struct vextype vertex;/*顶点信息*/int id;/*入度域*/edgenode link;/*边表头指针*/vexnode /*顶点表结点*/第13章 图vexnode gan;TOPOSORTB(vexnode ga)/*AOV网的邻接表*/int i,j,k,m=0,top=1;/*m为输出顶点个数计数器，top为栈指针*/for(i=0;iadjvex1;gak.id-;/*vk+1入度减1*/if(gak.id=0)/*将入度为0的