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