第7章 图结构

}

for(i=0;i

for(i=0;iadjvex]++; p=p->nextarc; } }

S.s=new int[num]; S.t=0;

for(i=0;i

(2) 拓扑排序的算法实现

函数void TopSort(ALGraph G)的功能是，根据有向图G的邻接表输出一个拓扑排序序列。 void TopSort(ALGraph G) { int *indegree,i,count=0; ArcNode* p; Stack S; Init_IndegreeStack(indegree,S,G); while(S.t) { count++; i=S.s[--S.t]; cout<adjvex]--; if(!indegree[p->adjvex]) S.s[S.t++]=p->adjvex; p=p->nextarc; } } cout<

void main()

{ ALGraph G; GKind gk=DG; cout<<\建立一个有向图的邻接表G:\\n\ CreateGraph_AL(G,gk); cout<<\有向图G的邻接表为:\\n\ DisplyAL(G);

-.215.-

第7章 图结构

cout<<\有向图G的一个拓扑排序序列为:\\n\ TopSort(G); }

程序的运行演示结果为：

建立一个有向图的邻接表G:

输入顶点数和边(弧)数vexnum arcnum:12 16↙ 按某种顺序输入12个顶点的值: 1 2 3 4 5 6 7 8 9 10 11 12↙

输入图中16条边(弧)的信息u v:

1 2 1 3 1 4 1 12 2 3 3 5 3 7 3 8 4 5 5 7 6 8 9 10 9 11 9 12 10 12 11 6↙ 有向图G的邻接表为: 0 (1): [11] [3] [2] [1] 1 (2): [2]

2 (3): [7] [6] [4]

3 (4): [4] 4 (5): [6] 5 (6): [7] 6 (7): 7 (8):

8 (9): [11] [10] [9] 9 (10): [11] 10 (11): [5] 11 (12):

有向图G的一个拓扑排序序列为: 9 10 11 6 1 2 3 8 4 5 7 12

程序运行中所建立的是图7.30(b)所示的有向图G的邻接表，其输出结果是G中所有顶点的一个拓扑排序序列。该算法的时间复杂度为O(n+e)。

7.7关键路径和关键活动

如前所述，可以利用对图的拓扑排序操作来判断工程能否顺利进行。现在从另一方面来考虑，设工程的每一个活动都有起始点、结束点、完成时间（即期限）。由于在整个工程内部，只有当一些活动完成了，另一些活动才能开始。这时，除了考虑各活动开始的顺序以外，还要考虑整个工程至少需要多少时间？哪些活动是影响工程进度的关键？这就是关键路径问题。求解图的关键路径是有向无环图的另一种应用。

7.7.1 AOE网及其相关概念

在带权有向图中，用顶点表示事件(event)，用弧表示活动(activity)，权表示活动的持续时间，这样组成的网称为以边表示活动的网(Activity On Edge)，简称为AOE网。

在AOE网中，通常只有一个入度为0的顶点和一个出度为0的顶点，这是因为一个工程只有一个开始点和一个完成点。入度为0的顶点称为起始点或源点，出度为0的顶点称为结束点或汇点。由于一个工程中的某些活动是可以并行的，所以从源点到汇点可能存在多条路径；从源点到汇点的最长路径的长度（即该路径上所有活动持续时间之和），就是完成整个工程所需的最少时间。称从源点到汇点具有最大长度的路径为关键路径(critical path)，关键路径上的所有活动称为关键活动。

例如，一个工程的AOE网如图7.34所示。在该网中，v0是源点，v8是汇点。假设图中权值的单位为天。活动a0需要5天完成，a1需要7天完成，a2需要3天完成，等等。当工程开始后，活动a0、a1可以同时进行，而只有活动a0完成后活动a2才能开始，只有活动a1完成后活动a3、a4才能启动，等等。顶点序列(v0,v2,v3,v4,v6,v8)组成的路径是图中所有路径中最长的，因此它是一条关键路径，该路径上的关键活动有：a1、a3、a5、a8、a10，其路径长度为24，即该项工程最少需要24天才能完成。而(v0,v2,v3,v4,v7,v8)也是一条关键路径，该路径上的关键活动有：a1、a3、a5、a9、a12。一个AOE网中，关键路径可能有多条，但所有关键路径的长度相同。

-.216.-