数据结构课件第六章

1、6.5 最短路径 (Shortest Path)图或网经常用于描述一个城市或城市间的交通运输网络，顶点表示一个城市或某个交通枢纽，边或弧表示两地之间的交通状况，边或弧上的权值可表示路程长度、交通费用或行程时间等等各种相关信息;当两个顶点之间存在多条路径时，其中必然存在一条“最短路径”，即路径中弧的权值和取最小值的那条路径；考虑到交通图的有向性，本节将讨论带权有向图(有向网)，并称路径中的第一个顶点为源点，路径中的最后一个顶点为终点。最短路径问题：如果从图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。问题解法 边上权值非

2、负情形的单源最短路径问题 Dijkstra算法 边上权值为任意值的单源最短路径问题 Bellman和Ford算法 所有顶点之间的最短路径 Floyd算法 边上权值非负情形的单源最短路径问题问题的提法： 给定一个带权有向图D与源点v，求从v到D中其它顶点的最短路径。限定各边上的权值大于或等于0。为求得这些最短路径，Dijkstra提出按路径长度的递增次序，逐步产生最短路径的算法。首先求出长度最短的一条最短路径，再参照它求出长度次短的一条最短路径，依次类推，直到从顶点v到其它各顶点的最短路径全部求出为止。举例说明Dijkstra逐步求解的过程首先，在这些最短路径中，长度最短的这条路径上必定只有一条

3、边，且它的权值是从源点出发的所有边上权的最小值。例如在下图中，从源点0出发有3条边，其中以边的权值为最小，由此0, 1不仅是从0到1的一条最短路径，并且它也是从源点到其它各终点的最短路径中长度为最短的。最短路径的特点分析：其次，第二条长度次短的最短路径只可能有两种情况：它或者只含一条从源点出发的边且边上的权值大于已求得最短路径的那条边的权值，但小于其它从源点出发的边上的权值；或者是一条只经过已求得最短路径的顶点的路径，换句话说，如果第一条长度最短的最短路径是从源点s到v1的话，若从v1到v2之间存在一条边，且路径s,v1,v2的长度比的权值小，则s,v1,v2就是第二条长度次短的最短路径。依次

4、类推，按迪杰斯特拉算法先后求得的每一条最短路径必定只有两种情况，或者是由源点直接到达终点，或者是只经过已经求得最短路径的顶点到达终点。 原图的顶点集为V，设置并逐步扩充一个集合S，存放已求出的最短路径的顶点，则尚未确定最短路径的顶点集合是V-S，为了直观起见，我们设想S中顶点均被涂成红色，V-S中的顶点均被涂成蓝色。算法初始化时，红点集中仅有一个源点，以后每一步都是按最短路径长度递增的顺序，逐个地把蓝点集中的顶点涂成红色后，加入到红点集中。算法的基本思想算法粗框：while ( S 中的红点数 n ) 在当前蓝点集中选择一个最短路径长度最短的 蓝点扩充到红点集中；那么，如何在蓝点集中选择一个最

5、短路径长度最短的蓝点呢？注意：这种蓝点所对应的最短路径上，除终点外，其余顶点都是红点。为此，对于图中每一个顶点i，都必须记住从v到i、且中间只经过红点的最短路径的长度，并将此长度记作i的距离值。 用数组Dn来存放n个顶点的距离值。开始时，红点集只有一个源点v，初始蓝点集中的蓝点j的距离值Dj均为有向边上的权值。若当前蓝点集中具有最小距离值的蓝点是k，则其距离值Dk就是k的最短路径长度，并且k是蓝点集中最短路径长度最短的顶点。注意：每个蓝点都有自己的距离值，只有距离值是最小的哪个蓝点，其距离值一定就是源点到它的最短路径，而其它蓝点的距离值不一定就是源点到自己的最短路径。证明： （距离值最小的Dk

6、是k的最短路径长度）若Dk不是k的最短路径长度，则必存在另外一条从源点v到k的路径P，其长度小于Dk。由距离值的定义可知，路径P上必然包含一个或多个蓝点作为中间点。假设从源点沿P向前第一次碰到的蓝点是x，则P上从源点v到x的这一段路径的长度，显然不小于x的距离值Dx。而P上从x到终点k所经过的边上，其权值均为非负实数，所以DxP的长度。又因为P的长度Dk(这是假设前提)，于是有下述不等式：Dx P的长度 Dk由此可知：Dx Dk，这与k是蓝点集中距离值最小的蓝点产生矛盾。所以Dk是k的最短路径长度。蓝点k蓝点x红点集S源点v前提：Dk Dx假设：P的长度 Dk推导：Dx P的长度 Dk矛盾证明

7、： （k是蓝点集中最短路径长度最短的顶点）设i是蓝点集中任何一个异于k的顶点，若i的最短路径只经过红点，则该最短路径长度是i的距离值Di,因为Dk是当前蓝点集距离值最小的顶点，所以DiDk。若i的最短路径P包含其它蓝点作为中间点，设P上第一个蓝点是j，则P上从v到j的路径长度就是j的距离值Dj。显然，DjDk，而P的长度=Dj+j到i的长度，因为j到i的长度为非负实数，所以 P的长度Dk。由此可知蓝点集中任意顶点i的最短路径长度都不会小于k的最短路径长度Dk。扩充红点集的方法：每一步只要在当前蓝点集中选择一个具有最小的距离值的蓝点k扩充到红点集合中k被涂成红色之后，剩余的蓝点的距离值可能由于增

8、加了新红点k而发生变化（即减少）。因此必须调整当前蓝点集中各蓝点的距离值。蓝点j红点集S源点vk蓝点j红点集S源点v蓝点k算法框架：S = v;置初始蓝点集中各蓝点的距离值；while ( S中红点数 n ) 1、在当前蓝点集中选择距离值最小的顶点k； 2、S = S + k; / 将k涂成红色加入红点集； 3、调整剩余蓝点的距离值。 若新红点k加入红点集S后，使得某个蓝点j的距离值Dj减少，则必定是由于存在一条从源点v途径新红点k最终到达蓝点j且中间只经过红点的、新的最短路径Pvkj。蓝点j红点集S源点vk如何调整剩余蓝点的距离值？Pvkj的长度小于从源点v到达j且中间只经过老红点（即不包含

9、k）的原最短路径Pvj的长度Dj。由于Pvkj是一条中间只经过红点的最短路径，所以，它的前一段从v到k的路径必定是k的最短路径，其长度为Dk；蓝点j红点集S源点vk它的后一段从k到j的路径Pkj只可能有两种情形其一是由k经过边直达蓝点j；其二是从k出发再经过S中若干老红点后到达j。可以证明后一种情形是不可能发生的。因此，调整蓝点j的距离值只须将原来的距离值与Dk+的长度进行比较，并取小者即可。假设从源点v出发，经过红点k、老红点x，最后到达蓝点j的新最短路径Pvkxj的长度小于原Dj。因为x比k先加入红点集S，故DxDk。又因为权值非负，所以从v到x的路径Pvx的长度不大于从v经k到x的路径P

10、vkx的长度，即 length(Pvk)=DxDk+length(Pkx)=length(Pvkx)因此从v经x到j的路径长度: length(Pvxj)=length(Pvk)+length(Pxj) 不大于从v经k、x到j的新路径长度 length(Pvkxj)=length(Pvkx)+length(Pxj)用反正法证明后一种情形是不可能的。又因为Pvxj中间只经过老红点，所以Pvxj的长度不大于Dj的值，由此可得： Djlength(Pvxj)length(Pvkxj)这与新路径Pvkxj的长度小于原Dj值的假设相矛盾！因此，使得Dj值减小的新路径比必是先经过老红点到达k，然后经过边直

11、达蓝点j的，它的长度是Dk+边上的权。 由此得到调整距离值的方法：当顶点k从蓝点集转移到红点集时，对蓝点集扫描检查，若某蓝点j的原距离值Dj大于新路径的长度Dk+边上的权，则将Dj修改成此长度值。蓝点j红点集S源点vk蓝点j红点集S源点vk数组S表示顶点集的颜色划分。Si=0表示顶点i为蓝点，Si=1表示顶点i为红点。引入一个辅助数组dist。它的每一个分量disti表示当前找到的从源点v0到终点vi的最短路径(距离值)的长度。初始状态：若从源点v0到顶点vi有边，则disti为该边上的权值；若从源点v0到顶点vi没有边，则disti为+ 。每次求得一条最短路径之后，其终点vk加入集合S，然后

12、对所有的viV-S，修改其disti值。为了记录最短路径，引入数组Path。如果顶点i在最短路径上，则Pathi=j表示在最短路径上，顶点i的前一个顶点为j。Dijkstra算法可描述如下：1、初始化： S v0; distjEdge0j, j = 1, 2, , n-1; /n为图中顶点个数2、找出距离值最短的顶点k： distkmindisti, iV-S; SS k ;3、修改V-S中（剩下）顶点的距离值： distimin disti, distk+Edgeki , 对于每一个iV-S; 4、判断：若S = V, 则算法结束，否则转2。Dijkstra算法中各辅助数组的变化Dijkst

13、ra算法的求解过程：01：路径长度1003：路径长度3002：路径长度5004：路径长度60templatevoid ShortestPath(Graph&G, T v, E dist, int path)/ Graph是一个带权有向图。本算法建立一个数组：distj,0=jn, 是当前求到的从顶点v到/顶点j的最短路径长度，同时用数组 pathj，0=jn，存放求到的最短路径。 int n=G.NumberOfVertices(); bool *S=new booln; /最短路径顶点集 int i, j; E w, min; for (i=0; in; i+) disti = G.getW

14、eight(v, i); /距离数组初始化 Si = false; /终点数组初始化 if (i!=v & distimaxValue) pathi=v; /路径数组初始化 else pathi = -1; Sv=true; distv=0; /顶点v加入顶点集合计算从单个顶点到其它各个顶点的最短路径 for (i=0; in-1; i+) min=maxValue, int u=v; /选不在S中具有最短路径的顶点u for (j=0; jn-1; j+) if (Sj= =flase & distjmin) u=j; min=disj; Su=ture; /将顶点u加入集合S for (k

15、=0; kn; k+) /调整不在S中的其他顶点的最短路径 w=G.GetWeight(u,k); if (Sk= =flase & wmaxValue & distu+wdistk) /顶点k未加入S，且经过u可以缩短路径 distk=distu+w; pathk=u; /修改到k的最短路径 ； Dijkstra算法中各辅助数组的变化 如何从表中读取源点0到终点v的最短路径？举顶点4为例： path4=2path2=3path3=0，反过来排列，得到路径0, 3, 2, 4，这就是源点0到终点4的最短路径。通过演示观察求最短路径的过程void printShortestPath(Graph&

16、G, int v, E dist, int path) cout“从顶点”G.getValue(v)“到替他各顶点的最短路径 为：”endl; int i, j, k, n=G.NumberOfVertices(); int *d=new intn; /临时存放最短路径上的各顶点 for (i=0; in; i+) if (i != v) j=i; k=0; while (j != v) dk+=j; j=pathj; cout “顶点” G.getValue(i) “到其他各顶点的最短路径为：” 0) cout G.getValue(d-k)“； cout“最短路径长度为” disti en

17、dl; delete d; 从path数组读取最短路径的算法Dist、S、path数组初始化：O(n)选择一个蓝点加入红点集：O(n) 1、在蓝点集中选择红点：O(n) 2、调整剩余蓝点的距离值：O(n)所以：总的时间复杂度：O(n2)算法的时间复杂度分析例求如图所示的有向图中从v1到其他各顶点的最短路径。v1v2v4v3v6v5v7235725533751v1v2v3v4v5v6v7002/v15/v13/v1/v1 /v1 /v112/v14/v23/v1 /v19/v2 /v124/v23/v18/v49/v2 /v134/v27/v39/v2 /v147/v39/v214/v559/v

18、214/v5614/v5v1v2v4v3v6v5v7235725533751v1到v2的最短路径为v1v2，长度为2；v1到v3的最短路径为v1v2v3，长度为4；v1到v4的最短路径为v1v4，长度为3；v1到v5的最短路径为v1v2v3v5 ，长度为7；v1到v6的最短路径为v1v2v6 ，长度为9；v1到v7的最短路径为v1v2v3v5v7，长度为14；v1v2v3v4v5v6v70025312/v1439243/v18934/v27947/v391459/v214614/v5例 求如图所示的有向图中从v0到其他各顶点的最短路径。v0v1v2v3v5v4214157236v0v1v2v3

19、v5v4214157236v0v1v2v3v4v5001/v04/v0/v0 /v0 /v011/v03/v18/v16/v1 /v023/v18/v14/v2 /v037/v44/v210 /v447/v49 /v359/v3v0到v1的最短路径为v0v1，其权为1；v0到v2的最短路径为v0v1v2，其权为3；v0到v3的最短路径为v0v1v2v4v3，其权为7；v0到v4的最短路径为v0v1v2v4 ，其权为4；v0到v5的最短路径为v0v1v2v4v3v5 ，其权为9；v0v1v2v3v4v5001411/v038623/v184374/v21047/v4959/v3边上权值为任意值的

20、单源最短路径问题带权有向图D的某几条边或所有边的长度可能为负值。利用Dijkstra算法，不一定能得到正确的结果。源点0到终点2的最短路径应是0, 1, 2，其长度为2，它小于算法中计算出来的dist2的值。 若设源点v = 0，使用Dijkstra算法，所得到的结果是不对的。Bellman和Ford提出了从源点逐次绕过其它顶点，以缩短到达终点的最短路径长度的方法。该方法有一个限制条件，即要求图中不能包含有由带负权值的边组成的回路。当图中没有由带负权值的边组成的回路时，有n个顶点的图中任意两个顶点之间如果存在最短路径，此路径最多有n-1条边。我们将以此为依据考虑计算从源点v到其它顶点u的最短路

21、径的长度distu。 Bellman-Ford方法构造一个最短路径长度数组序列dist1u，dist2u，distn-1u。其中，dist1 u是从源点v到终点u的只经过一条边的最短路径的长度，dist1u = Edgevu；dist2u是从源点v最多经过两条边到达终点u的最短路径的长度，dist3u是从源点v出发最多经过不构成带负长度边回路的三条边到达终点u的最短路径的长度，distn-1u是从源点v出发最多经过不构成带负长度边回路的n-1条边到达终点u的最短路径的长度。算法的最终目的是计算出distn-1u。可以用递推方式计算distku。 dist1u=Edgevu； distku=mi

22、ndistk-1u, mindistk-1j+ Edgeju设已经求出 distk-1j, j = 0, 1, , n-1, 此即从源点v最多经过不构成带负长度边回路的k-1条边到达终点j的最短路径的长度。从图的邻接矩阵中可以找到各个顶点j到达顶点u的距离Edgeju，计算 mindistk-1j+ Edgeju，可得从源点v绕过各个顶点，最多经过不构成带负长度边回路的k条边到达终点u的最短路径的长度。用它与distk-1u比较，取小者作为distku的值。 图的最短路径长度templatevoid Bellman-Ford(Graph&G, int v, E dist, int path)/

23、在有向带权图中有的边具有负的权值。从顶点v找到 所有其他顶点的最短路径。 int i, k, u, n=G.NumberOfVertices(); E w; for (i=0; in; i+) disti=G.getWeight(v, i); if (i!=v & distimaxValue) pathi=v; else pathi=-1; 计算最短路径的Bellman和Ford算法 for (k=2; kn; k+) for (u=0; un; u+) if (u!=v) for (i=0; i0 & wdisti+w) distu=disti+w; pathu=i; ;所有顶点之间的最短路

24、径(Floyd算法)如果希望求得图中任意两个顶点之间的最短路径，显然只要依次将每个顶点设为源点，调用迪杰斯特拉算法n次便可求出，其时间复杂度为O(n3)。弗洛伊德提出了另外一个算法，虽然其时间复杂度也是 O(n3)，但算法形式更简单。问题的提法：已知一个各边权值均大于0的带权有向图，对每一对顶点vi vj，要求求出vi与vj之间的最短路径和最短路径长度。Floyd算法的基本思想： 定义一个n阶方阵序列： A(-1), A(0), , A(n-1). 其中:k = 0,1, n-1算法说明:对于顶点i和j： 1、首先，考虑从i到j是否有以顶点0为中间点的路径：i，0，j。即考虑图中是否有边和，若

25、有，则新路径i，0，j的长度是Ci0+C0j，比较路径i，j和i，0，j的长度，并以较短者作为当前所求得的最短路径。该路径是中间点序号不大于0的最短路径。2、其次，考虑从i到j是否包含顶点1为中间点的路径：i，.，1，.，j。即找出从i到j的中间点序号不大于1的最短路径。 3、然后，再选择顶点2加入当前求得的从i到j中间点序号不大于1的最短路径中，按上述步骤进行比较。即从未加入顶点2作中间点的最短路径和加入顶点2作中间点的新路径中选取较小者，作为当前求得的从i到j的中间点序号不大于2的最短路径。通过演示观察Floid算法的执行过程4、依此类推，直到考虑了顶点n加入当前从i到j的最短路径后，选出

26、从i到j的中间点序号不大于n的最短路径为止。由于图中顶点序号不大于n，所以从i到j的中间点序号不大于n的最短路径，已考虑了所有顶点作为中间点的可能性。因而它必是从i到j的最短路径。templatevoid Floyd(Graph&G, E a, int path)/aij是顶点i到j之间的最短路径长度。Pathij是相 对路径上顶点j的前一顶点的顶点号。 int i, j, k, n = G.NumberOfVertices(); for (i=0; in; i+) /矩阵a与path初始化 for (j=0; jn; j+) aij = G.getWeight(i,j); if (i!=j

27、& aijmaxValue) pathij=i; else pathij=0; 所有各对顶点之间的最短路径 for (k=0; kn; k+) /针对每一个k，产生A(k)及path(k) for (i=0; in; i+) for (j=0; jn; j+) if (aik+akj 10a03 = 4a01 = 1a13 = 2 4 3a23 = 7a21 = 4a13 = 2 7 6 Path数组中Pathij=k的含义为：从i到j的最短路径上，j的前一个顶点为k。以Path(3)为例，对最短路径的读法加以说明。从A(3)知，顶点1到0的最短路径长度为a10 = 11,其最短路径看 pat

28、h10 = 2，path12 = 3，path 13 = 1, 表示顶点0 顶点2 顶点3 顶点1;从顶点1到顶点0最短路径为,。Floyd算法允许图中有带负权值的边，但不许有包含带负权值的边组成的回路。本章给出的求解最短路径的算法不仅适用于带权有向图，对带权无向图也可以适用。因为带权无向图可以看作是有往返二重边的有向图，只要在顶点vi 与vj 之间存在无向边(vi , vj )，就可以看成是在这两个顶点之间存在权值相同的两条有向边和。 数组a和path初始化：O(n2)对a中任意两个顶点i、j：O(n2) 对所有顶点k， 检查+是否小于： O(n) 如果是，调整i、j的距离所以：总的时间复杂

29、度：O(n3)算法的时间复杂度分析Floyd算法的应用顶点可达问题定义：图G的传递闭包矩阵A+是一个矩阵，且满足：如果存在一条长度 0的从i到j的路径则A+ij =1，否则A+ij =0。 定义：图G的自反传递闭包矩阵A*是一个矩阵，且满足：如果存在一条长度0的从i到j的路径则A*ij =1，否则A*ij =0。 问题：对于所有顶点对i和j，确定从i到j是否存在一条路径。对于左面的有向图，A、A+、A*如下所示：显然，A+和A*的差别仅在对角线上，A*ii =1总是成立的。 for (k=0; kn; k+) for (i=0; in; i+) for (j=0; jn; j+) if (ai

30、k=1&akj=1) aij= 1;简化函数Floyd算法，其中，若i到k可达且k到j可达，则i到j可达。算法结束时，最终的a就是A+。将A+中对角线元素全部设置为1则可得到A*。进一步的说明：若A(0)i,j=1，则顶点i到顶点j之间存在一条长度为1的路径。若A(1)i,j=1，则顶点i到顶点j之间存在一条长度不大于2的路径。若A(2)i,j=1，则顶点i到顶点j之间存在一条长度不大于3的路径。6.6 活动网络(Activity Network)一个无环的有向图称作有向无环图，简称DAG图，它在工程计划和管理方面有着广泛而重要的应用。除最简单的情况之外，几乎所有的工程(project)都可分

31、为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定的时序关系的约束。对整个工程，人们关心的是两方面的问题：一是工程能否顺利进行；二是完成整个工程所必须的最短时间。对应到有向图即为进行拓扑排序和求关键路径。 例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可以并行地学习。 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1

32、C9 计算机原理 C8 课程代号课程名称先修课程 C1 高等数学 C2 程序设计基础 C3 离散数学 C1, C2 C4 数据结构 C3, C2 C5 高级语言程序设计 C2 C6 编译方法 C5, C4 C7 操作系统 C4, C9 C8 普通物理 C1 C9 计算机原理 C8 课程代号课程名称先修课程学生课程学习工程图可以用有向图表示一个工程。在这种有向图中，用顶点表示活动，用有向边表示活动之间的先后关系。Vi必须先于活动Vj进行。这种有向图叫做顶点表示活动的网络(Activity On Vertices)。 在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边，AOV网络中不

33、能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动的开始应以自己的结束作为先决条件。因此，对给定的AOV网络，必须先判断它是否存在有向环。用顶点表示活动的网络 (AOV网络)检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。 这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环

34、，此AOV网络所代表的工程是不可行的。 例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为： C1, C2, C3, C4, C5, C6, C8, C9, C7或 C1, C8, C9, C2, C5, C3, C4, C7, C6进行拓扑排序的方法0、输入AOV网络。令n为顶点个数。1、在AOV网络中选一个没有直接前驱的顶点,并输出之; 2、从图中删去该顶点, 同时删去所有它发出的有向边; 重复以上1、2两步, 直到全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环。这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时A

35、OV网络中必定存在有向环。拓扑排序的过程 最后得到的拓扑有序序列为 C4 , C0 , C3 , C2 , C1 , C5 。它满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。问题:1、如何判断某顶点是否有直接前驱？ -根据顶点的入度进行判断。2、如何方便地去掉某顶点到所有直接后继的边？ -构造图的出边表。3、如何快速的找到入度为0的顶点？ -利用栈存储所有入度为0的顶点。AOV网络及其邻接表表示出边表，count记录顶点的入度拓扑排序算法框架Stack S; /建立入度为零的顶点栈for (图的所有顶点) if (顶点i的入度为零) 顶点号i

36、进栈S；count=0; /设置输出顶点计数器while (当栈S不空时) 从栈S退出一个顶点v；输出v； count+; /输出顶点计数器加1 for (顶点v的所有邻接顶点w) 将w入度减1; if (顶点w入度减至零) w进栈S； if (输出顶点个数count网络顶点个数n) 报告网络中存在有向环;增设一个数组count ，记录各个顶点入度。入度为零的顶点即无前驱的顶点。在输入数据前，入度数组count 初始化。在输入数据时，每输入一条边，就需要统计入度信息： cin i j; while (i-1&i-1&ji j; int *count =new intn; for ( int i

37、 = 0; i n; i+ ) counti=0; /入度数组在拓扑排序算法中，使用一个存放入度为零的顶点的链式栈，供选择和输出无前驱的顶点。只要出现入度为零的顶点，就将它加入栈中。使用这种栈的拓扑排序算法可以描述如下： (1) 建立入度为零的顶点栈; (2) 当入度为零的顶点栈不空时, 重复执行 从顶点栈中退出一个顶点, 并输出之;从AOV网络中删去这个顶点和它发出的边, 边的终顶点入度减一;如果边的终顶点入度减至0, 则该顶点进入度为零的顶点栈; (3) 如果输出顶点个数少于AOV网络的顶点个数, 则报告网络中存在有向环。在算法实现时，为了节省存储空间，可以直接利用count 数组作为栈的

38、空间，设立了一个栈顶指针top，指示当前栈顶的位置。栈初始化时置top = -1，表示空栈。将顶点i进栈时，采用头插法，执行以下指针的修改：countw = top; top = w;/top指向新栈顶w, 原栈顶元素位置放在countw中退栈操作可以写成：v = top; top = counttop;/位于栈顶的顶点的位置记于v, top退到次栈顶 class Graph /图的邻接表的类定义friend class Vertex;friend class Edge;private: Vertex *NodeTable; int *count; int n;public: Graph (

39、const int vertices = 0 ) : n ( vertices ) NodeTable = new vertexn; count = new intn; ; void TopologicalOrder ( ); void TopologicalSort (Graph&G) int i, j, w, v; int top = -1; /入度为零的顶点栈初始化 int n=G.NumberOfVertices(); int *count =new intn; for ( int i = 0; i i j; while (i-1&i-1&ji j; for ( i = 0; i n;

40、 i+ ) /初始化栈 if (counti=0) counti=top; top=i;拓扑排序的算法 for ( i = 0; i n; i+ ) /期望输出n个顶点 if ( top = -1 ) /中途栈空,转出 cout “网络中有回路(有向环) endl; return; else /继续拓扑排序 v = top; top = counttop; /退栈 cout G.getValue(v) endl; /输出 w = G.GetFirstNeighbor(); while ( w ) /扫描该顶点的出边表 if ( -countw = 0 ) /该顶点入度减一 countw = t

41、op; top = w; /减至零 w = G.GetNextNeighbor(v, w); 分析此拓扑排序算法可知，如果AOV网络有n个顶点，e条边，在拓扑排序的过程中，搜索入度为零的顶点，建立链式栈所需要的时间是O(n)。在正常的情况下，有向图有n个顶点，每个顶点进一次栈，出一次栈，共输出n次。顶点入度减一的运算共执行了e次（入度减一意味着去掉一条边）。所以总的时间复杂度为O(n+e)。用边表示活动的网络(AOE网络)如果在无有向环的带权有向图中 用有向边表示一个工程中的各项活动(Activity) 用边上的权值表示活动的持续时间(Duration) 用顶点表示事件(Event)则这样的有

42、向图叫做用边表示活动的网络，简称AOE (Activity On Edges)网络。AOE网络中有唯一的起点（源点）和唯一的终点（汇点）。AOE网络在某些工程估算方面非常有用。例如，可以使人们了解： (1)完成整个工程至少需要多少时间(假设网络中没有 环)? (2)为缩短完成工程所需的时间, 应当加快哪些活动?在AOE网络中, 有些活动顺序进行，有些活动并行进行。从源点到各个顶点，以及从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。完成不同路径上的活动所需的时间虽然不同，但只有各条路径上所有活动都完成了，整个工程才算完成。因此，完成整个工程所需的时间取决于从源点到汇点的最长路径长

43、度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。 要找出关键路径，必须找出关键活动，即不按期完成就会影响整个工程完成的活动。关键路径上的所有活动都是关键活动。因此，只要找到了关键活动，就可以找到 关键路径定义几个与计算关键活动有关的量 事件Vi的最早可能开始时间Vei： 是从源点V0到顶点Vi的最长路径长度。 事件Vi的最迟允许开始时间Vli： 是在保证汇点Vn-1在Ven-1时刻完成的前提下， 事件Vi的允许的最迟开始时间。活动ak的最早可能开始时间Aek： 设活动ak在边上，则Aek是从源点V0到顶点Vi的最长路径长度。因此，A

44、ek=Vei。定义几个与计算关键活动有关的量 活动ak的最迟允许开始时间Alk： Alk是在不会引起时间延误的前提下，该活动允许 的最迟开始时间。 Alk=Vlj - dur()。 其中，dur()是完成ak所需的时间。 时间余量Alk - Aek： 表示活动ak的最早可能开始时间和最迟允许开始时间的时间余量。Alk = Aek表示活动ak是没有时间余量的关键活动。为找出关键活动, 需求出各个活动的Aek与Alk，以判别是否lk = ek；为求得Aek与Alk，需要先求得从源点V0到各个顶点Vi的Vei和Vli；求Vei的递推公式 从Ve0=0开始，由起点向终点递推S2，i = 1, 2, ,

45、 n-1。其中， S2是所有指向顶点Vi的有向边的集合。（可以理解成由从源点到Vi的最长路径决定）ij1j2j3j4取其中最大值从Vln-1=Ven-1开始，由终点向起点递推 S1, i=n-2, n-3, , 0 其中, S1是所有从顶点Vi发出的有向边的集合。这两个递推公式的计算必须分别在拓扑有序及逆拓扑有序的前提下进行。ij1j2j3j4取其中最小值计算关键路径时，可以一边进行拓扑排序一边计算各顶点的Vei。为了简化算法，假定在求关键路径之前已经对各顶点实现了拓扑排序，并按拓扑有序的顺序对各顶点重新进行了编号。算法在求Vei, i=0, 1, , n-1时按拓扑有序的顺序计算，在求Vli

46、, i=n-1, n-2, , 0时按逆拓扑有序的顺序计算。设活动ak(k=1,2,e)在带权有向边上,它的持续时间用dur()表示，则有： Aek=Vei； Alk=Vlj-dur() k=1,2,e。这样就得到计算关键路径的算法。事件 Vei Vli V0 0 0 V1 6 6 V2 4 6 V3 5 8 V4 7 7 V5 7 10 V6 16 16 V7 14 14 V8 18 18 边 活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11Ae 0 0 0 6 4 5 7 7 7 16 14 Al 0 2 3 6 6 8 7 7 10 16 14Al-Ae 0 2

47、 3 0 2 3 0 0 3 0 0关键 是 是 是 是 是 是通过演示观察求关键路径的过程v4v0v1v2v3v5v6v7v8465112974426405771614181814108661670v4v0v1v6v7v87 边 活动 a1 a2 a3 a4 a5 a6 a7 a8 a9 a10 a11 e 0 0 0 6 4 5 7 7 7 16 14 l 0 2 3 6 6 8 7 7 10 16 14l - e 0 2 3 0 2 3 0 0 3 0 0关键 是 是 是 是 是 是程序实现时，计算最早开始时间是对所有顶点，逐个计算其后继顶点的最早开始时间。具体到某个后继顶点，则是在计算

48、值和已有值之间取大者。计算最迟开始时间是对所有顶点，逐个计算其前驱顶点的最迟开始时间。具体到某个前驱顶点，则是在计算值和已有值之间取小者。templatevoid CriticalPath(Graph&G) int i, j, k; E Ae, Al, w; int n= G.NumberOfVertices( ); E *Ve=new En; E *Vl=new En; for (i=0; in; i+) Vei=0;计算关键路径算法 for (i=0; iVej) Vej=Vei+w; j= G.getNextNeighbor(i,j); Vln-1=Ven-1; /? for (j=n-2; i0; j-) /逆向计算Vl k= G.getFirstNeighbor(j); while (k!=-1) w= G.geWeight(j,k); if (Vlk-wVlj) Vlj= Vlk-w; k= G.getNextNeighbor(i, k); for (i=0; in; i+) /求各活动的e, l j= G.getFirstNeighbor(i); while (j!=-1) Ae=Vei