图论中的概念及重要算法

1、图论中的概念及重要算法常州一中 林厚从ch1、图论中的基本概念一、 图的概念简单讲，一个图是由一些点和这些点之间的连线组成的。严格意义讲，图是一种数据结构，定义为：graph=（V，E），V是点（称为“顶点”）的非空有限集合，E是线（称为“边”）的集合，边一般用（vx，vy）表示，其中vx，vy属于V。图（A）共有4个顶点、5条边，表示为：V=v1，v2，v3，v4，E=（v1，v2），（v1，v3），（v1，v4），（v2，v3），（v2，v4）二、 无向图和有向图如果边是没有方向的，称此图为“无向图”，如图（A）和图（C），用一对圆括号表示无向边，如图（A）中的边（v1，v2），显然（vx

2、，vy）和（vy，vx）是两条等价的边，所以在上面E的集合中没有再出现边（v2，v1）。 如果边是有方向（带箭头）的，则称此图为“有向图”，如图（B），用一对尖括号表示有向边，如图（B）中的边<v1，v2>。把边<Vx，Vy>中Vx称为起点，Vy称为终点。显然此时边<vx，vy>与边<vy，vx>是不同的两条边。有向图中的边又称为弧，起点称为弧头，终点称为弧尾。图（B）表示为：V=v1，v2，v3，E=<v1，v2>，<v1，v3>，<v2，v3>，<v3，v2>如果两个顶点U、V之间有一条边相连，

3、则称U、V这两个顶点是关联的。三、 带权图一个图中的两顶点间不仅是关联的，而且在边上还标明了数量关系，如图（C），这种数量关系可能是距离、费用、时间、电阻等等，这些数值称为相应边的权。边上带有权的图称为带权图，也称为网（络）。四、 阶图中顶点的个数称为图的阶。图（A）、图（B）、图（C）的阶分别为4、3、5。五、 度图中与某个顶点相关联的边的数目，称为该顶点的度。度为奇数的顶点称为奇点，度为偶数的顶点称为偶点。图（A）中顶点v1，v2是奇点，v3，v4是偶点。在有向图中，把以顶点V为终点的边的数目称为顶点V的入度，把以顶点U为起点的边的数目称为顶点U的出度，出度为0的顶点称为终端顶点。如图（B

4、）中顶点v1的入度是0、出度是2，v2的入度是2、出度是1，v3的入度是2、出度是1，没有终端顶点。 定理1：无向图中所有顶点的度之和等于边数的2倍，有向图中的所有顶点的入度之和等于所有顶点的出度之和。 定理2：任意一个无向图一定有偶数个(或0个)奇点。六、 完全图若无向图中的任意两个顶点之间都存在着一条边，有向图中的任意两个顶点之间都存在着方向相反的两条边，则称此图为完全图。n阶完全有向图含有n*(n-1)条边，n阶完全无向图含有 n*(n-1)/2条边，当一个图接近完全图时，称为稠密图；相反，当一个图的边很少时，称为稀疏图。七、 子图设有两个图G =（V，E）和G=（V，E），若V是V的子

5、集，E是E的子集，则称G为G的子图。八、 路（径）在一个G =（V，E）的图中，从顶点v到顶点v的一条路径是一个顶点序列vi0，vi1，vi2，, vim，其中 vi0 = v， vim = v，若此图是无向图，则(vij-1，vij)E，1jm；若此图是有向图，则<vij-1，vij>E，1jm。路径长度是指路径上的边或弧的数目。序列中顶点不重复出现的路径称为简单路径，顶点v和顶点v相同的路径称为回路（或环）。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路（或简单环）。九、连通图在无向图G中，如果从顶点U到顶点V有路径，则称U和V是连通的。如果对于图G中

6、的任意两个顶点U和V都是连通的，则称图G是连通图，否则称为非连通图。在有向图G中，如果对于任意两个顶点U和V，从U到V和从V到U都存在路径，则称图G是强连通图。Ch2、图的存储结构一、 邻接矩阵表示法邻接矩阵是表示顶点之间相邻关系的矩阵，设G=V，E是一个度为n的图（顶点序号分别用1，2，n表示），则G的邻接矩阵是一个n阶方阵，Gi,j的值定义如下：1或权值 当vi与vj之间有边或弧时，取值为1或权值G i，j = 0或 当vi与vj之间无边或弧时，取值为0或（无穷大）上面3个图对应的邻接矩阵分别如下： 0 1 1 1 0 1 1 5 8 3G（A）= 1 0 1 1 G（B）= 0 0 1

7、G（C）= 5 2 6 1 1 0 0 0 1 0 8 2 10 4 1 1 0 0 10 11 3 6 4 11 采用邻接矩阵表示图，直观方便，很容易查找图中任两个顶点i和j之间有无边（或弧），以及边上的权值，只要看Ai,j的值即可，因为可以根据i,j的值随机查找存取，所以时间复杂性为O（1）。也很容易计算一个顶点的度（或入度、出度）和邻接点，其时间复杂性均为O（n）。但是，邻接矩阵表示法的空间复杂性为O（n*n），如果用来表示稀疏图，则会造成很大的空间浪费。二、边集数组表示法边集数组是利用一维数组存储图中所有边的一种图的表示方法。每个数组元素存储一条边的起点、终点和权值（如果有的话）。在边

8、集数组中查找一条边或一个顶点的度都需要扫描整个数组，所以其时间复杂性为O（e），e为边数。这种表示方法适合那些对边依次进行处理的运算，而不适合对顶点的运算和对任意一条边的运算。从空间复杂性上讲，边集数组适合于存储稀疏图。三、邻接表表示法（链式存储法）邻接表表示法是指对图中的每个顶点vi（1in）建立一个邻接关系的单链表，并把它们的表头指针用一维向量数组存储起来的一种图的表示方法。为每个顶点vi（1in）建立的单链表，是表示以该顶点为起点的所有边的信息（包括一个终点（邻接点）序号、一个权值和一个链接域）。一维向量数组除了存储每个顶点的表头指针外，还要存储该顶点的编号i。图（C）的邻接表表示为：图

9、的邻接表表示法便于查找任一顶点的关联边及邻接点，只要从表头向量中取出对应的表头指针，然后进行查找即可。由于无向图的每个顶点的单链表平均长度为2e/n，所以查找运算的时间复杂性为O(e/n)。对于有向图来说，想要查找一个顶点的后继顶点和以该顶点为起点的边、包括求该顶点的出度都很容易；但要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了，需要扫描整个表，时间复杂度为O（n+e）。所以，对于经常查找顶点入度或以该顶点为终点的关联边的运算时，可以建立一个逆邻接表，该表中每个顶点的单链表存储的是所有以该点为终点的关联边信息。甚至还可以把邻接表和逆邻接表结合起来，构造出“十字邻接表”

10、，此时，每个边结点的数据信息包含五个域：起点、终点、权、以该顶点为终点的关联边的链接、以该顶点为起点的关联边的链接。表头向量的结点也包括三个域：顶点编号、以该点为终点的表头指针域、以该点为起点的表头指针域。Ch3、图的遍历一、 概念从图中某一顶点出发系统地访问图中所有顶点，使每个顶点恰好被访问一次，这种运算操作被称为图的遍历。为了避免重复访问某个顶点，可以设一个标志数组visitedi，未访问时值为false，访问一次后就改为true。图的遍历分为深度优先遍历和广度（宽度）优先遍历两种方法。后面的函授将专门讲解。这儿我们先作个介绍。二、深度优先遍历从图中某个顶点Vi出发，访问此顶点并作已访问标

11、记，然后从Vi的一个未被访问过的邻接点Vj出发再进行深度优先遍历，当Vi的所有邻接点都被访问过时，则退回到上一个顶点Vk，再从Vk的另一个未被访问过的邻接点出发进行深度优先遍历，直至图中所有顶点都被访问到为止。如下面的左图从顶点a出发，进行深度优先遍历的结果为：a，b，c，d，e，g，f；右图从V1出发进行深度优先遍历的结果为：V1，V2，V4，V8，V5，V3，V6，V7。三、广度（宽度）优先遍历从图中某个顶点V0出发，访问此顶点，然后依次访问与V0邻接的、未被访问过的所有顶点，然后再分别从这些顶点出发进行广度优先遍历，直到图中所有被访问过的顶点的相邻顶点都被访问到。若此时图中还有顶点尚未被

12、访问，则另选图中一个未被访问过的顶点作为起点，重复上述过程，直到图中所有顶点都被访问到为止。如上面的左图从顶点a出发，进行广度优先遍历的结果为：a，b，d，e，f，c，g；右图从顶点V1出发，进行广度优先遍历的结果为：V1，V2，V3，V4，V5，V6，V7，V8。两种遍历方法相比，深度优先遍历实际上是尽可能地走“顶点表”；而广度优先遍历是尽可能沿顶点的“边表”进行访问，然后再沿边表对应顶点的边表进行访问，因此，有关边表的顶点需要保存(用队列，先进先出)，以便进一步进行广度优先遍历。ch4、图的重要算法一、 求图的最小生成树算法如果图G=（V，E）是一个连通的无向图，则把它的全部顶点V和一部分

13、边E构成一个子图G，即G=（V， E），且边集E能将图中所有顶点连通又不形成回路，则称子图G是图G的一棵生成树。同一个图可以有不同的生成树，但可以证明：n个顶点的连通图的生成树必定含有n-1条边。对于加权连通图（连通网），生成树的权即为生成树中所有边上的权值总和，权值最小的生成树称为图的最小生成树。求图的最小生成树具有很高的实际应用价值，比如要在若干个城市之间建一个交通网，要求各个城市都能到达且造价最低，这就是一个典型的最小生成树问题。那么如何求（最小）生成树呢？求（最小）生成树可以从某个顶点采用深度优先遍历的方法，也可采用广度优先遍历的方法，分别称为深度优先生成树和广度优先生成树。上图中的图

14、（B）和图（C）所示两棵生成树，是对图（A）分别进行深度优先遍历和广度优先遍历得到的一棵生成树。也可以综合应用深度优先遍历和广度优先遍历的特定算法，如：Prim算法和Kruskal算法，下面我们将分别介绍。1、用Prim算法求最小生成树的思想如下：（设图G的度为n，G=（V，E）设置一个顶点的集合S和一个边的集合TE，S和TE的初始状态均为空集；选定图中的一个顶点K，从K开始生成最小生成树，将K加入到集合S；重复下列操作，直到选取了n-1条边： 选取一条权值最小的边（X，Y），其中XS，not (YS)；将顶点Y加入集合S，边（X，Y）加入集合TE；得到最小生成树T =（S，TE）下面给出Pr

15、im算法构造图的最小生成树的具体算法框架。 从文件中读入图的邻接矩阵g； 边集数组elist初始化；For i:=1 To n-1 Do Begin elisti.fromv:=1；elisti.endv:=i+1；elisti.weight:=g1,i+1； End； 求出最小生成树的n-1条边； For k:=1 To n-1 Do Begin min:=maxint；m:=k； For j:=k To n-1 Do 查找权值最小的一条边 If elistj.weight<min Then Begin min:=elistj.weight；m:=j；End； If m<>

16、k Then Begin t:=elistk；elistk:=elistm；elistm:=t；End；把权值最小的边调到第k个单元 j:=elistk.endv； j为新加入的顶点 For i:=k+1 To n-1 Do 修改未加入的边集 Begin s:=elisti.endv； w:=gj,s； If w<elisti.weight Then Begin elisti.weight:=w；elisti.fromv:=j；End； End； End； 输出；2、用Kruskal算法求最小生成树的思想如下：（设图G的度为n，G=（V，E）设最小生成树为T=（V，TE），设置边的集合T

17、E的初始状态为空集。将图G中的边按权值从小到大排好序，然后从小的开始依次选取，若选取的边使生成树T不形成回路，则把它并入TE中，保留作为T的一条边；若选取的边使生成树形成回路，则将其舍弃；如此进行下去，直到TE中包含n-1条边为止。最后的T即为最小生成树。Kruskal算法在实现过程中的关键和难点在于：如何判断欲加入的一条边是否与生成树中已保留的边形成回路？我们可以将顶点划分到不同的集合中，每个集合中的顶点表示一个无回路的连通分量，很明显算法开始时，把所有n个顶点划分到n个集合中，每个集合只有一个顶点，表明顶点之间互不相通。当选取一条边时，若它的两个顶点分属于不同的集合，则表明此边连通了两个不

18、同的连通分量，因每个连通分量无回路，所以连通后得到的连通分量仍不会产生回路，因此这条边应该保留，且把它们作为一个连通分量，即把它的两个顶点所在集合合并成一个集合。如果选取的一条边的两个顶点属于同一个集合，则此边应该舍弃，因为同一个集合中的顶点是连通无回路的，若再加入一条边则必然产生回路。下面给出利用Kruskal算法构造图的最小生成树的具体算法框架。 将图的存储结构转换成边集数组表示的形式elist，并按照权值从小到大排好序； 设数组C1.n-1用来存储最小生成树的所有边，Ci是第i次选取的可行边在排好序的elist中的下标； 设一个数组S1.n，Si都是集合，初始时Si= i 。 i:=1；

19、获取的第i条最小生成树的边j:=1；边集数组的下标While i<=n-1 Do Begin For k:=1 To n Do Begin 取出第j条边，记下两个顶点分属的集合序号 If elistj.fromv in sk Then m1:=k； If elistj.endv in sk Then m2:=k； End； If m1<>m2 Then Begin 找到的elist第j条边满足条件，作为第i条边保留 Ci:=j； i:=i+1； sm1:=sm1+sm2；合并两个集合 sm2:= ； 另一集合置空 End； j:=j+1； 取下条边，继续判断 End； 输出最

20、小生成树的各边：elistCi二、求图的最短路径算法在带权图G=（V，E）中，若顶点 Vi,Vj是图G的两个顶点，从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和。从顶点Vi到Vj可能有多条路径，其中路径长度最小的一条路径称为顶点Vi到Vj的最短路径。求最短路径具有很高的实用价值，在各种竞赛中经常遇到。一般有两类最短路径问题：一类是求从某个顶点（源点）到其它顶点（终点）的最短路径；另一类是求图中每一对顶点间的最短路径。对于不带权的图，只要人为的把每条边加上权值1，即可当作带权图一样处理了。1、从一个顶点到其余各顶点的最短路径看上图，假设C1,C2,C3,C4,C5,C6是六座城市，他们之

21、间的连线表示两城市间有道路相通，连线旁的数字表示路程。请编写一程序，找出C1到Ci的最短路径(2i6)，输出路径序列及最短路径的路程长度。对于一个含有n个顶点和e条边的图来说，从某一个顶点Vi到其余任一顶点Vj的最短路径，可能是它们之间的边（Vi，Vj），也可能是经过k个中间顶点和k+1条边所形成的路径(1kn-2)。下面给出解决这个问题的Dijkstra算法思想。设图G用邻接矩阵的方式存储在GA中，GAi,j=maxint表示Vi，Vj是不关联的，否则为权值（大于0的实数）。设集合S用来保存已求得最短路径的终点序号，初始时S=Vi表示只有源点，以后每求出一个终点Vj，就把它加入到集合中并作为

22、新考虑的中间顶点。设数组dist1.n用来存储当前求得的最短路径，初始时Vi，Vj如果是关联的，则distj等于权值，否则等于maxint，以后随着新考虑的中间顶点越来越多，distj可能越来越小。再设一个与dist对应的数组path1.n用来存放当前最短路径的边，初始时为Vi到Vj的边，如果不存在边则为空。执行时，先从S以外的顶点（即待求出最短路径的终点）所对应的dist数组元素中，找出其值最小的元素（假设为distm），该元素值就是从源点Vi到终点Vm的最短路径长度，对应的pathm中的顶点或边的序列即为最短路径。接着把Vm并入集合S中，然后以Vm作为新考虑的中间顶点，对S以外的每个顶点V

23、j，比较distm+GAm,j的distj的大小，若前者小，表明加入了新的中间顶点后可以得到更好的方案，即可求得更短的路径，则用它代替distj，同时把Vj或边（Vm，Vj）并入到pathj中。重复以上过程n-2次，即可在dist数组中得到从源点到其余各终点的最段路径长度，对应的path数组中保存着相应的最段路径。对于上图，采用Dijkstra算法找出C1到Ci之间的最短路径(2i6)的过程如下：初始时：123456Dist048maxintmaxintmaxintPathC1C1,C2C1,C3第一次：选择m=2，则S=C1,C2，计算比较dist2+GA2,j与distj的大小（3j6）1

24、23456Dist047810maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C5第二次：选择m=3，则S=C1,C2,C3，计算比较dist3+GA3,j与distj的大小（4j6）123456Dist04789maxintPathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5第三次：选择m=4，S=C1,C2,C3,C4，计算比较dist4+GA4,j与distj的大小（5j6）123456Dist0478917PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C4,C6第四次：选择m=5，则S=C1

25、,C2,C3,C4,C5，计算比较dist5+GA5,j与distj的大小（j=6）123456Dist0478913PathC1C1,C2C1,C2,C3C1,C2,C4C1,C2,C3,C5C1,C2,C3,C5,C6因为该图的度n=6，所以执行n-2=4次后结束，此时通过dist和path数组可以看出：C1到C2的最短路径为：C1C2，长度为：4；C1到C3的最短路径为：C1C2C3，长度为：7；C1到C4的最短路径为：C1C2C4，长度为：8；C1到C5的最短路径为：C1C2C3C5，长度为：9；C1到C6的最短路径为：C1C2C3C5C6，长度为：13；下面给出具体的Dijkstra

26、算法框架（注：为了实现上的方便，我们用一个一维数组s1.n代替集合S，用来保存已求得最短路径的终点集合，即如果sj=0表示顶点Vj不在集合中，反之，sj=1表示顶点Vj已在集合中）。Procedure Dijkstra(GA,dist,path,i)； 表示求Vi到图G中其余顶点的最短路径，GA为 图G的邻接矩阵，dist和path为变量型参数，其中path的基类型为集合BeginFor j:=1 To n Do Begin 初始化 If j<>i Then sj:=0 Else sj:=1； distj:=GAi,j； If distj<maxint maxint为假设的一

27、个足够大的数 Then pathj:=i+jElse pathj:= ； End；For k:=1 To n-2 Do Begin w:=maxint；m:=i； For j:=1 To n Do 求出第k个终点Vm If (sj=0) and (distj<w) Then Begin m:=j；w:=distj； End； If m<>i Then sm:=1 else exit；若条件成立，则把Vm加入到S中，否则退出循环，因为剩余的终点，其最短路径长度均为maxint，无需再计算下去 For j:=1 To n Do 对sj=0的更优元素作必要修改 If (sj=0)

28、and (distm+GAm,j<distj) Then Begin Distj:=distm+GAm,j；pathj:=pathm+j； End； End；End；2、任意一对顶点之间的最短路径这个问题的解法有两种：一是分别以图中的每个顶点为源点共调用n次Dijkstra算法，这种算法的时间复杂度为O（n3）；另外还有一种算法：Floyed算法，它的思路简单，但时间复杂度仍然为O（n3），下面介绍Floyed算法。设具有n个顶点的一个带权图G的邻接矩阵用GA表示，再设一个与GA同类型的表示每对顶点之间最短路径长度的二维数组A，A的初值等于GA。Floyed算法需要在A上进行n次运算，每

29、次以Vk（1kn）作为新考虑的中间点，求出每对顶点之间的当前最短路径长度，最后依次运算后，A中的每个元素Ai，j就是图G中从顶点Vi到顶点Vj的最短路径长度。再设一个二维数组P1.n,1.n，记录最短路径，其元素类型为集合类型set of 1.n。Floyed算法的具体描述如下：Procedure Floyed(GA，A，P)； Begin For i:=1 To n Do 最短路径长度数组和最短路径数组初始化 For j:=1 To n Do Begin Ai,j:=GAi,j； If Ai,j<maxint Then pi,j:=i+jElse pi,j:= ； End； For k

30、:=1 To n Do n次运算 For i:=1 To n Do For j:=1 To n Do Begin If (i=k)or(j=k)or(i=j) Then Continue； 无需计算，直接进入下一轮循环 If Ai,k+Ak,j<Ai,j Then Begin 找到更短路径、保存 Ai,j：= Ai,k+Ak,j； Pi,j：= Pi,k+Pk,j； End； End； End；对于上图，大家可以运用Floyed算法，手工或编程找出任意一对顶点之间的最短路径及其长度。三、拓扑排序算法在日常生活中，一项大的工程可以看作是由若干个子工程（这些子工程称为“活动”）组成的集合，这

31、些子工程（活动）之间必定存在一些先后关系，即某些子工程（活动）必须在其它一些子工程（活动）完成之后才能开始，我们可以用有向图来形象地表示这些子工程（活动）之间的先后关系，子工程（活动）为顶点，子工程（活动）之间的先后关系为有向边，这种有向图称为“顶点活动网络”，又称“AOV网”。在AOV网中，有向边代表子工程（活动）的先后关系，即有向边的起点活动是终点活动的前驱活动，只有当起点活动完成之后终点活动才能进行。如果有一条从顶点Vi到Vj的路径，则说Vi是Vj的前驱，Vj是Vi的后继。如果有弧<Vi，Vj>，则称Vi是Vj的直接前驱，Vj是Vi的直接后继。一个AOV网应该是一个有向无环图

32、，即不应该带有回路，否则必定会有一些活动互相牵制，造成环中的活动都无法进行。把不带回路的AOV网中的所有活动排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，这个过程称为“拓扑排序”，所得到的活动序列称为“拓扑序列”。需要注意的是AOV网的拓扑序列是不唯一的，如对下图进行拓扑排序至少可以得到如下几种拓扑序列：02143567、01243657、02143657、01243567。 在上图所示的AOV网中，工程1和过程2显然可以同时进行，先后无所谓；但工程4却要等工程1和工程2都完成以后才可进行；工程3要等到工程1和工程4完成以后才可进行；工程5又要等到工程3、工程4完成以后才可进

33、行；工程6则要等到工程4完成后才能进行；工程7要等到工程3、工程5、过程6都完成后才能进行。可见由AOV网构造拓扑序列具有很高的实际应用价值。其实，构造拓扑序列的拓扑排序算法思想很简单：只要选择一个入度为0的顶点并输出，然后从AOV网中删除此顶点及以此顶点为起点的所有关联边；重复上述两步，直到不存在入度为0的顶点为止，若输出的顶点数小于AOV网中的顶点数，则输出“有回路信息”，否则输出的顶点序列就是一种拓扑序列。对上图进行拓扑排序的过程如下：1、 选择顶点0（唯一）， 输出0， 删除边<0，1>，<0，2>；2、 选择顶点1（不唯一，可选顶点2）， 输出1， 删除边&l

34、t;1，3>，<1，4>；3、 选择顶点2（唯一）， 输出2， 删除边<2，4>；4、 选择顶点4（唯一）， 输出4， 删除边<4，3>，<4，5>，<4,6>；5、 选择顶点3（不唯一，可选顶点6）， 输出3， 删除边<3，5>，<3，7>；6、 选择顶点5（不唯一，可选顶点6）， 输出5， 删除边<5，7>；7、 选择顶点6（唯一）， 输出6， 删除边<6，7>；8、 选择顶点7（唯一）， 输出7， 结束。输出的顶点数m=8，与AOV网中的顶点数n=8相等，所以输出一种拓扑序列

35、：01243567。为了算法实现上的方便，我们采用邻接表存储AOV网，不过稍做修改，在顶点表中增加一个记录顶点入度的域id，具体的拓扑排序算法描述如下：Procedure TopSort(dig:graphlist)；用邻接表dig存储图GVar n,top,i,j,k,m: Integer；P:graphlist；Begin n:=dig.adjv； 取顶点总个数 top:=0； 堆栈、初始化 For i:=1 To n Do 对入度为0的所有顶点进行访问，序号压栈If dig.adji.id = 0 Then Begin dig.adji.id:=top； top:=i； End； m:=

36、0； 记录输出的顶点个数 While top<>0 Do 栈不空Begin j:=top； 取一个入度为0的顶点序号 top:=dig.adjtop.id； 出栈、删除当前处理的顶点、指向下个入度为0的顶点 Write(dig.adjtop.v)； 输出顶点序号 m:=m+1； p:=dig.adjj.link； 指向Vj邻接表的第一个邻接点 While p<>nil Do 删除所有与Vj相关边 Begin k:=p.adjv； 下一个邻接点 dig.adjk.id:= dig.adjk.id - 1； 修正相应点的入度 If dig.adjk.id = 0 Then

37、Begin 入度为0的顶点入栈 dig.adjk.id:=top；top:=k； End； p:=p.next； 沿边表找下一个邻接点 End；End；If m<n Then Writeln(no solution!)； 有回路End；四、关键路径算法利用AOV网络，对其进行拓扑排序能对工程中活动的先后顺序作出安排。但一个活动的完成总需要一定的时间，为了能估算出某个活动的开始时间，找出那些影响工程完成时间的最主要的活动，我们可以利用带权的有向网，图中的边表示活动，边上的权表示完成该活动所需要的时间，一条边的两个顶点分别表示活动的开始事件和结束事件，这种用边表示活动的网络，称为“AOE网”

38、。其中，有两个特殊的顶点（事件），分别称为源点和汇点，源点表示整个工程的开始，通常令第一个事件（事件1）作为源点，它只有出边没有入边；汇点表示整个工程的结束，通常令最后一个事件（事件n）作为汇点，它只有入边没有出边；其余事件的编号为2到n-1。在实际应用中，AOE网应该是没有回路的，并且存在唯一的入度为0的源点和唯一的出度为0的汇点。下图表示一个具有12个活动的AOE网。图中有8个顶点，分别表示事件0到7，其中，0表示开始事件，7表示结束事件，边上的权表示完成该活动所需要的时间。AOE网络要研究的问题是完成整个工程至少需要多少时间？哪些活动是影响工程进度的关键？下面先讨论一个事件的最早发生时间

39、和一个活动的最早开始时间。如上图，事件Vj必须在它的所有入边活动eik（1kn）都完成后才能发生。活动eik（1kn）的最早开始时间是与它对应的起点事件Vik的最早发生时间。所有以事件Vj为起点事件的出边活动ejk（1km）的最早开始时间都等于事件Vj的最早发生时间。所以，我们可以从源点出发按照上述方法，求出所有事件的最早发生时间。设数组earliest1.n表示所有事件的最早发生时间，则我们可以按照拓扑顺序依次计算出earliestk：earliest1=0earliestk=maxearliestj+dutj,k (其中，事件j是事件k的直接前驱事件，dutj,k表示边<j，k>

40、;上的权)对于图5_10，用上述方法求earliest0.7的过程如下：earliest0=0earliest1=earliest0+dut0,1=0+6=6earliest2=earliest0+dut0,2=0+7=7earliest4=maxearliest1+dut1,4，earliest2+dut2,4=max6+5,7+4=11earliest3=maxearliest1+dut1,3，earliest4+dut4,3=max6+3,11+3=14earliest5=maxearliest3+dut3,5，earliest4+dut4,5=max14+2,11+4=16earlie

41、st6=earliest4+dut4,6=11+3=14earliest7=maxearliest3+dut3,7，earliest5+dut5,7, earliest6+dut6,7=max14+5,16+2,14+4=19最后得到的earliest7就是汇点的最早发生时间，从而可知整个工程至少需要19天完成。但是，在不影响整个工程按时完成的前提下，一些事件可以不在最早发生时间发生，而向后推迟一段时间，我们把事件最晚必须发生的时间称为该事件的最迟发生时间。同样，有些活动也可以推迟一段时间完成而不影响整个工程的完成，我们把活动最晚必须开始的时间称为该活动的最迟开始时间。一个事件在最迟发生时间内

42、仍没发生，或一个活动在最迟开始时间内仍没开始，则必然会影响整个工程的按时完成。如上图，事件Vj的最迟发生时间应该为：它的所有直接后继事件Vjk（1km）的最迟发生时间减去相应边<Vj，Vjk>上的权（活动ejk需要时间），取其中的最小值。且汇点的最迟发生时间就是它的最早发生时间，再按照逆拓扑顺序依次计算出所有事件的最迟发生时间，设用数组lastest1.n表示，即：lastestn=earliestnlastestj=minlastestk-dutj,k (其中，事件k是事件j的直接后继事件，dutj,k表示边<j，k>上的权)对于图5_10，用上述方法求lastest

43、 0.7的过程如下：lastest7=earliest7=19lastest6=lastest7-dut6,7=19-4=15lastest5=lastest7-dut5,7=19-2=17lastest3=minlastest5-dut3,5，lastest7-dut3,7 =min17-2,19-5 =14lastest4=minlastest3-dut4,3，lastest5-dut4,5, lastest6-dut4,6 =min14-3,17-4,15-3 =11lastest2=lastest4-dut2,4=11-4=7lastest1=minlastest3-dut1,3，la

44、stest4-dut1,4 =min14-3,11-5 =6lastest0=minlastest1-dut0,1，lastest2-dut0,2 =min6-6,7-7 =0计算好每个事件的最早和最迟发生时间后，我们可以很容易地算出每个活动的最早和最迟开始时间，假设分别用actearliest和actlastest数组表示，设活动i的两端事件分别为事件j和事件k,如下所示： 活动i 事件j > 事件k则：actearliesti=earliestjactlastesti=lastestk-dutj,k对于上面的例子，用上述方法求得所有活动的最早和最迟开始时间如下表：活动<0,1><0,2><1,3><1,4><2,4><3,5><3,7><4,3><4,5><4,6><5,7><6,7>最早0066714141111111614最迟00116715141113121715余量00500