拓扑排序
由某个集合上的一个偏序,得到该集合的一个全序,这个操作称为拓扑排序。这个说的偏数学了,对于有向无环图G做拓扑排序,是将G的顶点排成一个线性序列,使得图中任意顶点u,v,如果边(u,v)属于E(G),则u在线性序列中的位置处于v的前边。
对于一个流程图,可以用顶点表示活动,弧表示活动间的优先关系,这样所表示的有向图称为顶点表示活动的网,即AOV网。在网中,如果顶点i到顶点j有一条有向路径,或者(i,j)是一条弧,则i是j的前驱,j是i的后继。AOV网中不应该出现环。
拓扑排序的思想很简单,(1)在有向图中选一个没有前驱的顶点输出;(2)从途中删除该顶点和所有以它为尾的弧。重复上述两个步骤,直到全部顶点输出,或者图中不存在无前驱的顶点时,这说明图有环。
有拓扑排序算法可以看出,拓扑序列不唯一。
bool TopologicalSort(ALGraph *G){ //使用邻接存储 int indegree[G -> vexnum]; InitDegree(G, indegree); //求每个顶点的入度 stack<int> sta; int count = 0; for(int i; i < G -> vexnum; i++) if(!indegree[i]) sta.push(i); while(!sta.empty()){ sta.pop(); cout << i; count++; for(arcnode * p = G -> vex[i].firstarc; p; p = p -> nextarc){ int k = p -> adjvex; if(--indegree[k] == 0) sta.push(k); } } if(count == G -> vexnum) return true; else return false; }
关键路径
与AOV网不同,用边表示活动的网称为AOE网。AOE网是一个带权的有向无环图,用来估算工程完成的时间。由于整个工程只有一个开始点和一个完成点,所以网中只有一个入度为0的点(源点)和一个出度为0的点(汇点)。AOE网要研究的问题是完成整个工程最少需要多少时间,那些活动是影响工程的关键活动?
AOE网中的某些活动是可以并行的,所以完成工程的最短时间是从开始点到完成点的最长路径的长度,成为关键路径。用e(i)表示活动ai的最早开始时间,l(i)表示ai的最迟开始时间(在不影响整个工程的时间前提下),l(i)- e(i)表示活动ai的时间余量,l(i)= e(i)的活动称为关键活动,显然关键路径上的活动都是关键活动。算法如下:
- 输入e条弧,建立AOE网,可以用邻接表。
- 从源点v0出发,另ve【0] = 0,按拓扑有序求其余各顶点的最早发生时间ve[ i ],如果拓扑排序中序列顶点数小于网中顶点数,说明存在环。否则执行3
- 从汇点vn出发,另vl[n - 1] = ve[n - 1],按逆拓扑有序求各顶点最迟发生时间vl[ i ]。
- 根据ve和vl判断,e( i ) = ve[ i ], l(i) = vl(k) - w(j,k),w表示弧权值,如果e(i) = l(i),说明(j,K)是关键活动。
v1 | v2 | v3 | v4 | v5 | v6 | v7 | v8 | v9 | |
ve | 0 | 6 | 4 | 5 | 7 | 7 | 16 | 14 | 18 |
vl | 0 | 6 | 5 | 8 | 7 | 10 | 16 | 14 | 18 |
构成两条关键路径(v1, v2, v5, v7, v9)和(v1, v2, v5, v8, v9).