A
O
V
{rm AOV}
AOV 网：若用
D
A
G
{rm DAG}
DAG 图表示一个工程，其顶点表示活动，用有向边
<
V
i
,
V
j
>
{rm
拓扑排序：在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，称为该图的一个拓扑排序
1）每个顶点出现且只出现一次。
2）若顶点
A
A
A 在序列中排在顶点
B
B
B 的前面，则在图中不存在从顶点
B
B
B 到顶点
A
A
A 的路径。
或定义为：拓扑排序是对有向无环图的顶点的一种排序，它使得若存在一条从顶点
A
A
A 到顶点
B
B
B 的路径，则在排序中顶点
B
B
B 出现在顶点
A
A
A 的后面。每个
A
O
V
{rm AOV}
AOV 网都有一个或多个拓扑排序序列。
对一个
A
O
V
{rm AOV}
AOV 网进行拓扑排序的算法有很多，下面介绍比较常用的一种方法的步骤：
1）从
A
O
V
{rm AOV}
AOV 网中选择一个没有前驱的顶点并输出。
2）从网中删除该顶点和所有以它为起点的有向边。
3）重复步骤1和步骤2直到当前的
A
O
V
{rm AOV}
AOV 网为空或当前网中不存在无前驱的顶点为止。后一种情况说明有向图中必然存在环。
下图所示为拓扑排序过程的示例。每轮选择一个入度为0的顶点并输出，然后删除该顶点和所有以它为起点的有向边，最后得到拓扑排序的结果为 { 1 , 2 , 4 , 3 , 5 } {1, 2, 4, 3, 5 } {1,2,4,3,5}。
以以下有向无环图为例，实现拓扑排序算法：
算法步骤：
1）定义一个队列Q，并把所有入度为0的结点加入队列。
2）取队首结点，输出。然后删去所有从它出发的边，并令这些边到达的顶点的入度减1，如果某个顶点的入度减为0，则将其加入队列。
3）反复进行步骤2，直到队列为空。如果队列为空时入过队的结点数目恰好为N，说明拓扑排序成功，图G为有向无环图；否则，拓扑排序失败，图G中有环。
可使用邻接表实现拓扑排序。显然，由于需要记录结点的入度，因此需要额外建立一个数组inDegree[MAXV]，并在程序一开始读入图时就记录好每个结点的入度。接下来就只需要按上面所说的步骤进行实现即可。
详细实现代码（邻接表版）：
#include#include "queue" using namespace std; #define MaxVertexNum 100 //顶点数目的最大值 struct ArcNode { //边表结点 int adjvex; //该弧所指向的顶点的位置 ArcNode *next; //指向下一条弧的指针 }; template struct VNode { //顶点表结点 VertexType data; //顶点信息 ArcNode *first; //指向第一条依附该顶点的弧的指针 }; template class ALGraph { //ALGraph是以邻接表存储的图类型 private: VNode vertices[MaxVertexNum]; //邻接表 int vexnum, arcnum; //图的顶点数和弧数 int inDegree[MaxVertexNum]; //存储每个顶点的入度 vector topologicalOrder; //存储拓扑序列 public: ALGraph() { //初始化 for (int i = 0; i < MaxVertexNum; i++) { inDegree[i] = 0; vertices[i].first = NULL; } } void create() { int row, col; cin >> vexnum >> arcnum; //输入实际图的顶点数和边数 for (int i = 0; i < vexnum; i++) //输入顶点信息 cin >> vertices[i].data; for (int i = 0; i < arcnum; i++) { //输入边信息 cin >> row >> col; ArcNode *p = new ArcNode; p->adjvex = col; p->next = vertices[row].first; vertices[row].first = p; inDegree[col]++; //对应弧头的入度+1 } } bool topologicalSort() { int num = 0; //记录加入拓扑序列的顶点数 queue q; for (int i = 0; i < vexnum; i++) if (inDegree[i] == 0) q.push(i); //将所有入度为0的顶点入队 while (!q.empty()) { int u = q.front(); //取队首顶点u topologicalOrder.push_back(vertices[u].data); //顶点u加入拓扑序列 q.pop(); //队首出队 //检测顶点u的后继结点 ArcNode *p = vertices[u].first; while (p) { int v = p->adjvex; inDegree[v]--; //顶点v的入度减1 if (inDegree[v] == 0) //顶点v的入度减为0则入队 q.push(v); p = p->next; } num++; //加入拓扑序列的顶点数加1 } if (num < vexnum) return false; //排序失败，有向图中有回路 else return true; //拓扑排序成功 } //输出拓扑序列 void displayTopologicalOrder() { for (int i = 0; i < topologicalOrder.size(); i++) cout << topologicalOrder[i] << "t"; } }; int main() { ALGraph G; G.create(); bool flag = G.topologicalSort(); if (flag) { cout << "topologicalOrder:" << "t"; G.displayTopologicalOrder(); } return 0; }
输入数据：
5 7 v0 v1 v2 v3 v4 0 1 0 3 1 2 1 3 2 4 3 2 3 4
输出结果：
topologicalOrder: v0 v1 v3 v2 v4
由于输出每个顶点的同时还要删除以它为起点的边，故采用邻接表存储时拓扑排序的时间复杂度为 O ( ∣ V ∣ + ∣ E ∣ ) O(left | V right | + left | E right | ) O(∣V∣+∣E∣) ，采用邻接矩阵存储时拓扑排序的时间复杂度为 O ( ∣ V ∣ 2 ) O(left | V right |^2 ) O(∣V∣2)。
对一个
A
O
V
{rm AOV}
AOV 网，如果采用下列步骤进行排序，则称之为逆拓扑排序：
1）从
A
O
V
{rm AOV}
AOV 网中选择一个没有后继（出度为0）的顶点并输出。
2）从网中删除该顶点和所有以它为终点的有向边。
3）重复步骤1和步骤2直到当前的
A
O
V
{rm AOV}
AOV 网为空。
在带权有向图中，以顶点表示事件，以有向边表示活动，以边上的权值表示完成该活动的开销（如完成活动所需的时间），称之为用边表示活动的网络，简称
A
O
E
{rm AOE}
AOE 网络。
A
O
E
{rm AOE}
AOE 网和
A
O
V
{rm AOV}
AOV 网都是有向无环图，不同之处在于它们的边和顶点所代表的含义是不同的：
A
O
E
{rm AOE}
AOE 网中的边有权值
而
A
O
V
{rm AOV}
AOV 网中的边无权值，仅表示顶点之间的前后关系。
A
O
E
{rm AOE}
AOE 网具有以下两个性质：
1）只有在某顶点所代表的事件发生后，从该顶点出发的各有向边所代表的活动才能开始；
2）只有在进入某顶点的各有向边所代表的活动都已结束时，该顶点所代表的事件才能发生。
在
A
O
E
{rm AOE}
AOE 网中仅有一个入度为0的顶点，称为开始顶点（源点），它表示整个工程的开始；
网中也仅存在一个出度为0的顶点，称为结束顶点（汇点），它表示整个工程的结束。
在 A O E {rm AOE} AOE 网中，有些活动是可以并行进行的。从源点到汇点的有向路径可能有多条，并且这些路径长度可能不同。完成不同路径上的活动所需的时间虽然不同，但是只有所有路径上的活动都已完成，整个工程才能算结束。因此，从源点到汇点的所有路径中，具有最大路径长度的路径称为关键路径，而把关键路径上的活动称为关键活动。
完成整个工程的最短时间就是关键路径的长度，即关键路径上各活动花费开销的总和。这是因为关键活动影响了整个工程的时间，即若关键活动不能按时完成，则整个工程的完成时间就会延长。因此，只要找到了关键活动，就找到了关键路径，也就可以得出最短完成时间。
下面给出在寻找关键活动时所用到的几个参量的定义。
1.事件
v
k
{rm v_k}
vk 的最早发生时间
v
e
(
k
)
{rm ve(k)}
ve(k)：
它是指从源点
v
1
{rm v_1}
v1 到顶点
v
k
{rm v_k}
vk 的最长路径长度。事件
v
k
{rm v_k}
vk 的最早发生时间决定了所有从
v
k
{rm v_k}
vk 开始的活动能够开工的最早时间。可用下面的递推公式来计算：
v
e
{rm ve}
ve(源点)=0
v
e
(
k
)
=
M
a
x
{
v
e
(
j
)
+
W
e
i
g
h
t
(
v
j
,
v
k
)
}
{rm ve(k)=Max { ve(j) + Weight(v_j,v_k) }}
ve(k)=Max{ve(j)+Weight(vj,vk)} ，
v
k
{rm v_k}
vk 为
v
j
{rm v_j}
vj 的任意后继，
W
e
i
g
h
t
(
v
j
,
v
k
)
{rm Weight(v_j,v_k)}
Weight(vj,vk) 表示
<
v
j
,
v
k
>
{rm
计算
v
e
(
)
{rm ve()}
ve() 值时，按从前往后的顺序进行，可以在拓扑排序的基础上计算：
1）初始时，令
v
e
[
1
…
n
]
=
0
{rm ve[1 dots n]=0 }
ve[1…n]=0 。
2）输出一个入度为0的顶点
v
j
{rm v_j}
vj 时，计算它所有直接后继顶点
v
k
{rm v_k}
vk 的最早发生时间，若
v
e
[
j
]
+
W
e
i
g
h
t
(
v
j
,
v
k
)
>
v
e
[
k
]
{rm ve[j]+Weight(v_j,v_k)>ve[k]}
ve[j]+Weight(vj,vk)>ve[k] ，则
v
e
[
k
]
=
v
e
[
j
]
+
W
e
i
g
h
t
(
v
j
,
v
k
)
{rm ve[k]=ve[j]+Weight(v_j,v_k)}
ve[k]=ve[j]+Weight(vj,vk) 。以此类推，直至输出全部顶点。
2.事件
v
k
{rm v_k}
vk 的最迟发生时间
v
l
(
k
)
{rm vl(k)}
vl(k)： 3.活动
a
i
{rm a_i}
ai 的最早开始时间
e
(
i
)
{rm e(i)}
e(i) : 4.活动
a
i
{rm a_i}
ai 的最迟开始时间
l
(
i
)
{rm l(i)}
l(i) : 5.一个活动
a
i
{rm a_i}
ai 的最迟开始时间
l
(
i
)
{rm l(i)}
l(i) 和其最早开始时间
e
(
i
)
{rm e(i)}
e(i) 的差额
d
(
i
)
=
l
(
i
)
−
e
(
i
)
{rm d(i)=l(i)-e(i)}
d(i)=l(i)−e(i) 求关键路径的算法步骤如下： 求解关键路径的过程如下： 1）求
v
e
(
)
{rm ve()}
ve() ：初始
v
e
(
0
)
=
0
{rm ve(0)=0}
ve(0)=0 ，在拓扑排序输出顶点过程中，求得： 2）求
v
l
(
)
{rm vl()}
vl() ：初始
v
l
(
5
)
=
8
{rm vl(5)=8}
vl(5)=8 ，在逆拓扑排序出栈过程中，求得： 3）弧的最早开始时间
e
(
)
{rm e()}
e() 等于该弧的起点的顶点的
v
e
(
)
{rm ve()}
ve() 。 4）弧的最迟开始时间
l
(
i
)
{rm l(i)}
l(i) 等于该弧的终点的顶点的
v
l
(
)
{rm vl()}
vl() 减去该弧持续的时间。 5）根据
l
(
i
)
−
e
(
i
)
=
0
{rm l(i)-e(i)=0}
l(i)−e(i)=0 的关键活动，得到的关键路径为
(
v
0
,
v
2
,
v
3
,
v
5
)
{rm (v_0,v_2,v_3,v_5)}
(v0,v2,v3,v5) 。 对于关键路径，需要注意以下几点： 以以上有向无环图为例，实现关键路径算法（邻接表版）： 求解
v
e
{rm ve}
ve 数组： 这时会发现，如果想要获得
v
e
[
j
]
{rm ve[j]}
ve[j] 的正确值，
v
e
[
i
1
]
∼
v
e
[
i
k
]
{rm ve[i1] sim ve[ik]}
ve[i1]∼ve[ik] 必须已经得到。有什么办法能够在访问某个结点时保证它的前驱结点都已经访问完毕呢？没错，使用拓扑排序就可以办到。当按照拓扑序列计算
v
e
{rm ve}
ve 数组时，总是能保证计算
v
e
[
j
]
{rm ve[j]}
ve[j] 的时候
v
e
[
i
1
]
∼
v
e
[
i
k
]
{rm ve[i1] sim ve[ik]}
ve[i1]∼ve[ik] 都已经得到。但是这时又碰到另一个问题，通过前驱结点去寻找所有后继结点很容易，但是通过后继结点
V
j
{rm V_j}
Vj 去寻找它的前驱结点
V
i
1
∼
V
i
k
{rm V_{i1} sim V_{ik}}
Vi1∼Vik 似乎没有那么直观。一个比较好的办法是，在拓扑排序访问到某个结点
V
i
{rm V_i}
Vi 时，不是让它去找前驱结点来更新
v
e
[
i
]
{rm ve[i]}
ve[i]，而是使用
v
e
[
i
]
{rm ve[i]}
ve[i] 去更新其所有后继结点的
v
e
{rm ve}
ve 值。通过这个方法，可以让拓扑排序访问到
V
j
{rm V_j}
Vj 的时候，
V
i
1
∼
V
i
k
{rm V_{i1} sim V_{ik}}
Vi1∼Vik 一定都已经用来更新过
v
e
[
j
]
{rm ve[j]}
ve[j] ，此时的
v
e
[
j
]
{rm ve[j]}
ve[j] 便是正确值，就可以用它去更新
V
j
{rm V_j}
Vj 的所有后继结点的
v
e
{rm ve}
ve 值。 这部分代码如下所示： 求解
v
l
{rm vl}
vl 数组： 和
v
e
{rm ve}
ve 数组类似，如果需要算出
v
l
[
i
]
{rm vl[i]}
vl[i] 的正确值，
v
l
[
j
1
]
∼
v
l
[
j
k
]
{rm vl[j1] sim vl[jk]}
vl[j1]∼vl[jk] 必须已经得到。这个要求与
v
e
{rm ve}
ve 数组的刚好相反，也就是需要在访问某个结点时保证它的后继结点都已经访问完毕，而这可以通过使用逆拓扑序列来实现。幸运的是，不必再做一次逆拓扑排序来得到逆拓扑序列，而是可以通过颠倒拓扑序列来得到一组合法的逆拓扑序列。此时会反现，在上面实现拓扑排序的过程中使用了栈来存储拓扑序列，那么只需要按顺序出栈就是逆拓扑序列。而当访问逆拓扑序列中的每个事件
V
i
{rm V_i}
Vi 时，就可以遍历
V
i
{rm V_i}
Vi 的所有后继结点
V
j
1
∼
V
j
k
{rm V_{j1} sim V_{jk}}
Vj1∼Vjk ，使用
v
l
[
j
l
]
∼
v
l
[
j
k
]
{rm vl[jl] sim vl[jk]}
vl[jl]∼vl[jk]来求出
v
l
[
i
]
{rm vl[i]}
vl[i] 。 这部分代码如下所示： 用上面的结果计算各边（活动）的最早开始时间和最迟开始时间：
e
[
i
→
j
]
=
l
[
i
→
j
]
{rm e[i to j]=l[i to j]}
e[i→j]=l[i→j] 的活动即为关键活动。 全部代码如下： 输入数据： 输出结果：
它是指在不推迟整个工程完成的前提下，即保证它的后继事件
v
j
{rm v_j}
vj 在其最迟发生时间
v
l
(
j
)
{rm vl(j)}
vl(j) 能够发生时，该事件最迟必须发生的时间。可用下面的递推公式来计算：
v
l
{rm vl}
vl(汇点)=
v
e
{rm ve}
ve(汇点)
v
l
(
k
)
=
M
i
n
{
v
l
(
j
)
−
W
e
i
g
h
t
(
v
k
,
v
j
)
}
{rm vl(k)=Min{ vl(j)-Weight(v_k,v_j) }}
vl(k)=Min{vl(j)−Weight(vk,vj)} ，
v
k
{rm v_k}
vk 为
v
j
{rm v_j}
vj 的任意前驱
注意：在计算
v
l
(
k
)
{rm vl(k)}
vl(k) 时，按从后往前的顺序进行，可以在逆拓扑排序的基础上计算。
计算
v
l
(
)
{rm vl()}
vl() 值时，按从后往前的顺序进行，在上述拓扑排序中，增设一个栈以记录拓扑序列， 拓扑排序结束后从栈顶至栈底便为逆拓扑有序序列。过程如下：
1）初始时，令
v
l
[
1
…
n
]
=
v
e
[
n
]
{rm vl[1 dots n]=ve[n]}
vl[1…n]=ve[n] 。
2）栈顶顶点
v
j
{rm v_j}
vj 出栈，计算其所有直接前驱顶点
v
k
{rm v_k}
vk 的最迟发生时间，若
v
l
[
j
]
−
W
e
i
g
h
t
(
v
k
,
v
j
)
<
v
l
[
k
]
{rm vl[j]-Weight(v_k,v_j)
它是指该活动弧的起点所表示的事件的最早发生时间。若边
<
v
k
,
v
j
>
{rm
它是指该活动弧的终点所表示事件的最迟发生时间与该活动所需时间之差。若边
<
v
k
,
v
j
>
{rm
它是指该活动完成的时间余量，即在不增加完成整个工程所需总时间的情况下，活动
a
i
{rm a_i}
ai 可以拖延的时间。若一个活动的时间余量为零，则说明该活动必须要如期完成，否则就会拖延整个工程的进度，所以称
l
(
i
)
−
e
(
i
)
=
0
{rm l(i)-e(i)=0}
l(i)−e(i)=0 即
l
(
i
)
=
e
(
i
)
{rm l(i)=e(i)}
l(i)=e(i) 的活动
a
i
{rm a_i}
ai 是关键活动。
1）从源点出发，令
v
e
{rm ve}
ve(源点) = 0，按拓扑有序求其余顶点的最早发生时间
v
e
(
)
{rm ve()}
ve() 。
2）从汇点出发，令
v
l
{rm vl}
vl(汇点) =
v
e
{rm ve}
ve(汇点)，按逆拓扑有序求其余顶点的最迟发生时间
v
l
(
)
{rm vl()}
vl() 。
3）根据各顶点的
v
e
(
)
{rm ve()}
ve() 值求所有弧的最早开始时间
e
(
)
{rm e()}
e() 。
4）根据各顶点的
v
l
(
)
{rm vl()}
vl() 值求所有弧的最迟开始时间
l
(
)
{rm l()}
l() 。
5）求
A
O
E
{rm AOE}
AOE 网中所有活动的差额
d
(
)
{rm d()}
d()，找出所有
d
(
)
=
0
{rm d()=0}
d()=0 的活动构成关键路径。
v
0
{rm v_0}
v0
v
1
{rm v_1 }
v1
v
2
{rm v_2}
v2
v
3
{rm v_3}
v3
v
4
{rm v_4}
v4
v
5
{rm v_5}
v5
v
e
(
i
)
{rm ve(i)}
ve(i) 0 3 2 6 6 8
v
l
(
i
)
{rm vl(i)}
vl(i) 0 4 2 6 7 8
a
0
{rm a_0}
a0
a
1
{rm a_1}
a1
a
2
{rm a_2}
a2
a
3
{rm a_3}
a3
a
4
{rm a_4}
a4
a
5
{rm a_5}
a5
a
6
{rm a_6}
a6
a
7
{rm a_7}
a7
e
(
i
)
{rm e(i)}
e(i) 0 0 3 3 2 2 6 6
l
(
i
)
{rm l(i)}
l(i) 1 0 4 4 2 5 6 7
l
(
i
)
−
e
(
i
)
{rm l(i)-e(i)}
l(i)−e(i) 1 0 1 1 0 3 0 1
v
e
(
1
)
=
3
{rm ve(1)=3}
ve(1)=3 ，
v
e
(
2
)
=
2
{rm ve(2)=2}
ve(2)=2 ，
v
e
(
3
)
=
m
a
x
{
v
e
(
1
)
+
2
,
v
e
(
2
)
+
4
}
=
m
a
x
{
5
,
6
}
=
6
{rm ve(3)=max{ ve(1)+2,ve(2)+4 } =max { 5,6 }=6 }
ve(3)=max{ve(1)+2,ve(2)+4}=max{5,6}=6 ，
v
e
(
4
)
=
6
{rm ve(4)=6}
ve(4)=6 ，
v
e
(
5
)
=
m
a
x
{
v
e
(
2
)
+
3
,
v
e
(
3
)
+
2
,
v
e
(
4
)
+
1
}
=
m
a
x
{
5
,
8
,
7
}
=
8
{rm ve(5)=max{ ve(2)+3,ve(3)+2,ve(4)+1 }=max{ 5,8,7 }=8}
ve(5)=max{ve(2)+3,ve(3)+2,ve(4)+1}=max{5,8,7}=8
v
l
(
4
)
=
7
{rm vl(4)=7}
vl(4)=7，
v
l
(
3
)
=
6
{rm vl(3)=6}
vl(3)=6，
v
l
(
2
)
=
m
i
n
{
v
l
(
3
)
−
4
,
v
l
(
5
)
−
3
}
=
m
i
n
{
2
,
5
}
=
2
{rm vl(2)=min{ vl(3)-4,vl(5)-3 }=min{ 2,5 }=2}
vl(2)=min{vl(3)−4,vl(5)−3}=min{2,5}=2 ，
v
l
(
1
)
=
m
i
n
{
v
l
(
3
)
−
2
,
v
l
(
4
)
−
3
}
=
m
i
n
{
4
,
4
}
=
4
{rm vl(1)=min{ vl(3)-2,vl(4)-3 }=min{4,4 }=4}
vl(1)=min{vl(3)−2,vl(4)−3}=min{4,4}=4，
v
l
(
0
)
=
m
i
n
{
v
l
(
1
)
−
3
,
v
l
(
2
)
−
2
}
=
m
i
n
{
1
,
0
}
=
0
{rm vl(0)=min{vl(1)-3,vl(2)-2 }=min{ 1,0 }=0}
vl(0)=min{vl(1)−3,vl(2)−2}=min{1,0}=0，注意：
v
l
(
0
)
{rm vl(0)}
vl(0) 必然为0而无须再求。
1）关键路径上的所有活动都是关键活动，它是决定整个工程的关键因素，因此可通过加快关键活动来缩短整个工程的工期。但也不能任意缩短关键活动，因为一旦缩短到一定的程度，该关键活动就可能会变成非关键活动。
2）网中的关键路径并不唯一，且对于有几条关键路径的网，只提高一条关键路径上的关键活动速度并不能缩短整个工程的工期，只有加快那些包括在所有关键路径上的关键活动才能达到缩短工期的目的。//拓扑排序，顺便求ve数组
bool topologicalSort() {
int num = 0; //记录加入拓扑序列的顶点数
queue
//根据逆拓扑序列，求得vl数组
void getVL() {
//找到ve数组的最大值，即汇点的ve值
int maxVE = -1;
for (int i = 0; i < vexnum; i++)
if (ve[i] > maxVE)
maxVE = ve[i];
//初始化vl数组，初值为汇点的ve值
for (int i = 0; i < vexnum; i++)
vl[i] = maxVE;
//直接使用topOrder出栈即为逆拓扑序列，求解vl数组
while (!topOrder.empty()) {
int u = topOrder.top(); //栈顶元素为u
topOrder.pop();
//遍历顶点u的后继结点
ArcNode *p = vertices[u].first;
while (p) {
int v = p->adjvex; //u的后继结点v
//用u的所有后继结点v的vl值来更新vl[u]
if (vl[v] - p->weight < vl[u])
vl[u] = vl[v] - p->weight;
p = p->next;
}
}
}
最早：
e
[
i
→
j
]
=
v
e
[
i
]
{rm e[i to j]=ve[i]}
e[i→j]=ve[i]
最迟：
l
[
i
→
j
]
=
v
l
[
j
]
−
l
e
n
g
t
h
[
i
→
j
]
{rm l[i to j]=vl[j]-length[i to j]}
l[i→j]=vl[j]−length[i→j]#include
6 8
v0 v1 v2 v3 v4 v5
0 1 3
0 2 2
1 3 2
1 4 3
2 3 4
2 5 3
3 5 2
4 5 1
ve: 0 3 2 6 6 8
vl: 0 4 2 6 7 8
e: 0 0 3 3 2 2 6 6
l: 1 0 4 4 2 5 6 7
critical path:
v0->v2
v2->v3
v3->v5
