算法 - 图的实例 - 拓扑排序与关键路径 (Topological Sort and Critical Path)
返回分类：全部文章 >> 基础知识
返回上级：编程基础 - 图 (Graph)
本文将介绍活动网络的基础知识，并用C++实现拓扑排序(Topological Sort)和关键路径(Critical Path)。
在查看本文之前，需要一些数据结构和程序语言的基础。
尤其是“矩阵”、“矩阵的压缩(matrix)”、“图(graph)”等的知识。
文章目录
算法 - 图的实例 - 拓扑排序与关键路径 (Topological Sort and Critical Path)1 拓扑排序与关键路径简述 (Introduction)2 拓扑排序 (Topological Sort)3 拓扑排序C++代码 (Topological Sort C++ Code)4 关键路径 (Critical Path)5 关键路径C++代码 (Critical Path C++ Code)5 主函数与测试 (Main Method and Testing)5.1 主函数 (Main Method)4.2 打印结果 (Print Output)
1 拓扑排序与关键路径简述 (Introduction)
AOV网络(Activity on Vertices)：用有向图表示一个工程，每一个顶点表示活动，用边表示活动方向，边开始的顶点是结束顶点的前置条件。
AOV网络不能有有向回路，即不能有有向环；将各个顶点排列成一个线性有序序列的运算，称为拓扑排序；如果网络存在有向环，则表示此工程不可行。
AOE网络(Activity on Edges)：用有向图表示一个工程，每一条边表示活动，用边上权值表示活动时间，顶点表示事件。
AOE网络不能有有向回路，即不能有有向环；完成整个工程所需的时间取决于从源点到汇点的最长路径长度，这条最长路径称为关键路径；关键路径上的活动称为关键活动。
2 拓扑排序 (Topological Sort)
拓扑排序方法：
（1）输入AOV网络；
（2）从AOV网路中选择一个没有直接前驱的顶点，输出；
（3）从图中删除该点，同时删除它所有的边；
（4）重复步骤（2）和（3），直到所有顶点均输出；或者还剩下顶点，表明此图存在有向环。
例如下图：没有前驱的顶点，只能是 V2 和 V4 。
V4
V0
V1
V5
V2
V3
所以拓扑排序顺序：
V2，V4，V0，……
V4，V2或V0， ……
3 拓扑排序C++代码 (Topological Sort C++ Code)
bool GetBeginVertexesAndIndegrees(AMGraphInt
* graph
,
std
::stack
<int>& vertexStack
,
std
::vector
<int>& indegrees
)
{
double infinity
= graph
->GetDefaultWeight();
int size
= graph
->GetVertexCount();
indegrees
.assign(size
, 0);
double weight
;
for (int c
= 0; c
< size
; c
++)
{
bool hasEdge
= false;
for (int r
= 0; r
< size
; r
++)
{
graph
->TryGetWeight(r
, c
, weight
);
if (weight
!= infinity
)
{
hasEdge
= true;
indegrees
[c
]++;
}
}
if (!hasEdge
)
{
vertexStack
.push(c
);
}
}
return !vertexStack
.empty();
}
bool TopologicalSort(AMGraphInt
* graph
,
std
::vector
<int>& paths
)
{
if (graph
== nullptr || !graph
->IsOriented())
{
return false;
}
paths
.clear();
int size
= graph
->GetVertexCount();
if (size
== 0)
{
return true;
}
double infinity
= graph
->GetDefaultWeight();
std
::stack
<int> vertexStack
;
std
::vector
<int> indegrees
;
if (!GetBeginVertexesAndIndegrees(graph
, vertexStack
, indegrees
))
{
return false;
}
double weight
;
for (int i
= 0; i
< size
; i
++)
{
if (vertexStack
.empty())
{
return false;
}
else
{
int vertex
= vertexStack
.top();
vertexStack
.pop();
paths
.push_back(vertex
);
for (int c
= 0; c
< size
; c
++)
{
graph
->TryGetWeight(vertex
, c
, weight
);
if (weight
!= infinity
&& --indegrees
[c
] == 0)
{
vertexStack
.push(c
);
}
}
}
}
return true;
}
4 关键路径 (Critical Path)
关键路径：从源点到汇点具有最大长度的路径；
关键活动：关键路径上的活动；
我们假设带权有向图中，顶点为 { v0, v1, …, vi, …, vn-1 } ，边为 { e0, e1, …, ej,… } 。
事件最早开始时间：顶点 vi 最早发生的时间；
事件最迟开始时间：顶点 vi 最迟发生的时间，如果超过这个时间，工程将延误；
活动的最早开始时间：边 ej 最早发生的时间；
活动的最迟开始时间：边 ej 最迟发生的时间，如果超过这个时间，工程将延误。
举例说明：
e0 = 9
e1 = 13
e2 = 15
e3 = 9
e4 = 29
e6 = 6
e5 = 7
e7 = 18
e8 = 6
e9 = 12
v0
v1
v2
v3
v5
v4
v6
v7
此图已经按拓扑排序编号。
事件最早活动时间 VE (Vertex Earliest Time) ：
V
E
(
v
0
)
=
0
V
E
(
v
1
)
=
v
0
+
e
0
=
0
+
9
=
9
V
E
(
v
2
)
=
v
0
+
e
1
=
0
+
13
=
13
V
E
(
v
3
)
=
max
(
v
1
+
e
2
,
v
2
+
e
3
)
=
max
(
9
+
15
,
13
+
9
)
=
24
V
E
(
v
4
)
=
v
3
+
e
6
=
24
+
6
=
30
V
E
(
v
5
)
=
max
(
v
2
+
e
4
,
v
3
+
e
5
)
=
max
(
13
+
29
,
24
+
7
)
=
42
V
E
(
v
6
)
=
max
(
v
4
+
e
7
,
v
5
+
e
8
)
=
max
(
30
+
18
,
42
+
6
)
=
48
V
E
(
v
7
)
=
v
6
+
e
9
=
48
+
12
=
60
\begin{array}{rlll} VE(v_0) &&&= 0 \\ VE(v_1) &= v_0 + e_0 &= 0 + 9 &= 9 \\ VE(v_2) &= v_0 + e_1 &= 0 + 13 &= 13 \\ VE(v_3) &= \max(v_1 + e_2, v_2 + e_3) &= \max(9 + 15, 13 + 9) &= 24 \\ VE(v_4) &= v_3 + e_6 &= 24 + 6 &= 30 \\ VE(v_5) &= \max(v_2 + e_4, v_3 + e_5) &= \max(13 + 29, 24 + 7) &= 42 \\ VE(v_6) &= \max(v_4 + e_7, v_5 + e_8) &= \max(30 + 18, 42 + 6) &= 48 \\ VE(v_7) &= v_6 + e_9 &= 48 + 12 &= 60 \end{array}
VE(v0)VE(v1)VE(v2)VE(v3)VE(v4)VE(v5)VE(v6)VE(v7)=v0+e0=v0+e1=max(v1+e2,v2+e3)=v3+e6=max(v2+e4,v3+e5)=max(v4+e7,v5+e8)=v6+e9=0+9=0+13=max(9+15,13+9)=24+6=max(13+29,24+7)=max(30+18,42+6)=48+12=0=9=13=24=30=42=48=60
事件最迟活动时间 VL (Vertex Lastest Time) ：
V
L
(
v
7
)
=
V
E
(
v
7
)
=
60
V
L
(
v
6
)
=
V
E
(
v
7
)
−
e
9
=
60
−
12
=
48
V
L
(
v
5
)
=
V
E
(
v
6
)
−
e
8
=
48
−
6
=
42
V
L
(
v
4
)
=
V
E
(
v
6
)
−
e
7
=
48
−
18
=
30
V
L
(
v
3
)
=
min
(
V
E
(
v
5
)
−
e
5
,
V
E
(
v
4
)
−
e
6
)
=
min
(
42
−
7
,
30
−
6
)
=
24
V
L
(
v
2
)
=
min
(
V
E
(
v
5
)
−
e
4
,
V
E
(
v
3
)
−
e
3
)
=
min
(
42
−
29
,
24
−
9
)
=
13
V
L
(
v
1
)
=
V
E
(
v
3
)
−
e
2
=
24
−
15
=
9
V
L
(
v
0
)
=
min
(
V
E
(
v
2
)
−
e
1
,
V
E
(
v
1
)
−
e
0
)
=
min
(
13
−
13
,
9
−
9
)
=
0
\begin{array}{rlll} VL(v_7) &= VE(v_7) &&= 60 \\ VL(v_6) &= VE(v_7) - e_9 &= 60 - 12 &= 48 \\ VL(v_5) &= VE(v_6) - e_8 &= 48 - 6 &= 42 \\ VL(v_4) &= VE(v_6) - e_7 &= 48 - 18 &= 30 \\ VL(v_3) &= \min(VE(v_5) - e_5, VE(v_4) - e_6) &= \min(42 - 7, 30 - 6) &= 24 \\ VL(v_2) &= \min(VE(v_5) - e_4, VE(v_3) - e_3) &= \min(42 - 29, 24 - 9) &= 13 \\ VL(v_1) &= VE(v_3) - e_2 &= 24 - 15 &= 9 \\ VL(v_0) &= \min(VE(v_2) - e_1, VE(v_1) - e_0) &= \min(13 - 13, 9 - 9) &= 0 \end{array}
VL(v7)VL(v6)VL(v5)VL(v4)VL(v3)VL(v2)VL(v1)VL(v0)=VE(v7)=VE(v7)−e9=VE(v6)−e8=VE(v6)−e7=min(VE(v5)−e5,VE(v4)−e6)=min(VE(v5)−e4,VE(v3)−e3)=VE(v3)−e2=min(VE(v2)−e1,VE(v1)−e0)=60−12=48−6=48−18=min(42−7,30−6)=min(42−29,24−9)=24−15=min(13−13,9−9)=60=48=42=30=24=13=9=0
活动的最早开始时间 WE (Weight Earliest Time) ：
W
E
(
e
0
)
=
V
E
(
v
0
)
=
0
W
E
(
e
1
)
=
V
E
(
v
0
)
=
0
W
E
(
e
2
)
=
V
E
(
v
1
)
=
9
W
E
(
e
3
)
=
V
E
(
v
2
)
=
13
W
E
(
e
4
)
=
V
E
(
v
2
)
=
13
W
E
(
e
5
)
=
V
E
(
v
3
)
=
24
W
E
(
e
6
)
=
V
E
(
v
3
)
=
24
W
E
(
e
7
)
=
V
E
(
v
4
)
=
30
W
E
(
e
8
)
=
V
E
(
v
5
)
=
42
W
E
(
e
9
)
=
V
E
(
v
6
)
=
48
\begin{array}{rllrll} WE(e_0) &= VE(v_0) &= 0 \\ WE(e_1) &= VE(v_0) &= 0 \\ WE(e_2) &= VE(v_1) &= 9 \\ WE(e_3) &= VE(v_2) &= 13 \\ WE(e_4) &= VE(v_2) &= 13 \\ WE(e_5) &= VE(v_3) &= 24 \\ WE(e_6) &= VE(v_3) &= 24 \\ WE(e_7) &= VE(v_4) &= 30 \\ WE(e_8) &= VE(v_5) &= 42 \\ WE(e_9) &= VE(v_6) &= 48 \\ \end{array}
WE(e0)WE(e1)WE(e2)WE(e3)WE(e4)WE(e5)WE(e6)WE(e7)WE(e8)WE(e9)=VE(v0)=VE(v0)=VE(v1)=VE(v2)=VE(v2)=VE(v3)=VE(v3)=VE(v4)=VE(v5)=VE(v6)=0=0=9=13=13=24=24=30=42=48
活动的最迟开始时间 WL (Weight Lastest Time) ：
W
L
(
e
0
)
=
V
L
(
v
1
)
−
e
0
=
9
−
9
=
0
W
L
(
e
1
)
=
V
L
(
v
2
)
−
e
1
=
13
−
13
=
0
W
L
(
e
2
)
=
V
L
(
v
3
)
−
e
2
=
24
−
15
=
9
W
L
(
e
3
)
=
V
L
(
v
3
)
−
e
3
=
24
−
9
=
15
W
L
(
e
4
)
=
V
L
(
v
5
)
−
e
4
=
42
−
29
=
13
W
L
(
e
5
)
=
V
L
(
v
5
)
−
e
5
=
42
−
7
=
35
W
L
(
e
6
)
=
V
L
(
v
4
)
−
e
6
=
30
−
6
=
24
W
L
(
e
7
)
=
V
L
(
v
6
)
−
e
7
=
48
−
18
=
30
W
L
(
e
8
)
=
V
L
(
v
6
)
−
e
8
=
48
−
6
=
42
W
L
(
e
9
)
=
V
L
(
v
7
)
−
e
9
=
60
−
12
=
48
\begin{array}{rlll} WL(e_0) &= VL(v_1) - e_0 &= 9 - 9 &= 0 \\ WL(e_1) &= VL(v_2) - e_1 &= 13 - 13 &= 0 \\ WL(e_2) &= VL(v_3) - e_2 &= 24 - 15 &= 9 \\ WL(e_3) &= VL(v_3) - e_3 &= 24 - 9 &= 15 \\ WL(e_4) &= VL(v_5) - e_4 &= 42 - 29 &= 13 \\ WL(e_5) &= VL(v_5) - e_5 &= 42 - 7 &= 35 \\ WL(e_6) &= VL(v_4) - e_6 &= 30 - 6 &= 24 \\ WL(e_7) &= VL(v_6) - e_7 &= 48 - 18 &= 30 \\ WL(e_8) &= VL(v_6) - e_8 &= 48 - 6 &= 42 \\ WL(e_9) &= VL(v_7) - e_9 &= 60 - 12 &= 48 \\ \end{array}
WL(e0)WL(e1)WL(e2)WL(e3)WL(e4)WL(e5)WL(e6)WL(e7)WL(e8)WL(e9)=VL(v1)−e0=VL(v2)−e1=VL(v3)−e2=VL(v3)−e3=VL(v5)−e4=VL(v5)−e5=VL(v4)−e6=VL(v6)−e7=VL(v6)−e8=VL(v7)−e9=9−9=13−13=24−15=24−9=42−29=42−7=30−6=48−18=48−6=60−12=0=0=9=15=13=35=24=30=42=48
我们列成表格对比，
Activity(Weight)0123456789
WE00913132424304248WL00915133524304248
你会看到，其中表格中
W
E
(
e
3
)
≠
W
L
(
e
3
)
WE(e_3) \neq WL(e_3)
WE(e3)̸=WL(e3) 和
W
E
(
e
5
)
≠
W
L
(
e
5
)
WE(e_5) \neq WL(e_5)
WE(e5)̸=WL(e5) ，这表明了 e3 和 e5 不是关键活动。
则我们将 e3 和 e5 删除后，得到两条关键路径：
{ v0, v1, v3, v4, v6, v7 }
v0
v1
v2
v3
v5
v4
v6
v7
{ v0, v2, v5, v6, v7 }
v0
v1
v2
v3
v5
v4
v6
v7
5 关键路径C++代码 (Critical Path C++ Code)
struct CriticalEdge
{
int firstVertex
;
int secondVertex
;
double weight
;
};
void GetDisableEdges(AMGraphInt
* graph
,
std
::vector
<std
::vector
<double>>& disableEdgesMatrix
)
{
double infinity
= graph
->GetDefaultWeight();
int size
= graph
->GetVertexCount();
std
::vector
<CriticalEdge
> edges
;
disableEdgesMatrix
.assign(size
, std
::vector
<double>(size
, infinity
));
double weight
;
for (int r
= 0; r
< size
; r
++)
{
for (int adj
= graph
->FirstNeighbor(r
);
adj
!= -1;
adj
= graph
->NextNeighbor(r
, adj
))
{
CriticalEdge edge
;
edge
.firstVertex
= r
;
edge
.secondVertex
= adj
;
graph
->TryGetWeight(r
, adj
, edge
.weight
);
edges
.push_back(edge
);
disableEdgesMatrix
[r
][adj
] = edge
.weight
;
}
}
std
::vector
<double> vertexEarliest(size
, 0.0);
for (int i
= 0; i
< edges
.size(); i
++)
{
vertexEarliest
[edges
[i
].secondVertex
] =
std
::max(vertexEarliest
[edges
[i
].secondVertex
],
vertexEarliest
[edges
[i
].firstVertex
] + edges
[i
].weight
);
}
std
::vector
<double> vertexLastest(vertexEarliest
);
for (int i
= 0; i
< edges
.size(); i
++)
{
vertexLastest
[edges
[i
].firstVertex
] =
std
::min(vertexLastest
[edges
[i
].firstVertex
],
vertexEarliest
[edges
[i
].secondVertex
] - edges
[i
].weight
);
}
for (int i
= 0; i
< edges
.size(); i
++)
{
if (vertexEarliest
[edges
[i
].firstVertex
]
!= vertexLastest
[edges
[i
].secondVertex
] - edges
[i
].weight
)
{
disableEdgesMatrix
[edges
[i
].firstVertex
][edges
[i
].secondVertex
] = infinity
;
}
}
}
bool CriticalPathRecursion(const std
::vector
<std
::vector
<double>>& matrix
,
std
::stack
<int>& loopStack
,
std
::vector
<bool>& mark
,
const double& infinity
,
int vertex
,
std
::vector
<std
::stack
<int>>& paths
)
{
if (mark
[vertex
])
{
return false;
}
mark
[vertex
] = true;
int outdegree
= 0;
for (int c
= 0; c
< matrix
.size(); c
++)
{
if (matrix
[vertex
][c
] != infinity
)
{
loopStack
.push(vertex
);
if (!CriticalPathRecursion(matrix
, loopStack
, mark
, infinity
, c
, paths
))
{
return false;
}
loopStack
.pop();
outdegree
++;
}
}
mark
[vertex
] = false;
if (outdegree
== 0)
{
loopStack
.push(vertex
);
paths
.push_back(loopStack
);
loopStack
.pop();
}
return true;
}
bool CriticalPath(AMGraphInt
* graph
,
std
::vector
<std
::stack
<int>>& paths
)
{
if (graph
== nullptr || graph
->GetVertexCount() == 0)
{
return false;
}
std
::vector
<std
::vector
<double>> matrix
;
GetDisableEdges(graph
, matrix
);
double infinity
= graph
->GetDefaultWeight();
int size
= graph
->GetVertexCount();
std
::stack
<int> vertexStack
;
std
::vector
<int> indegrees
;
if (!GetBeginVertexesAndIndegrees(graph
, vertexStack
, indegrees
))
{
return false;
}
std
::stack
<int> loopStack
;
std
::vector
<bool> marks(size
, false);
while (!vertexStack
.empty())
{
if (!CriticalPathRecursion(matrix
,
loopStack
,
marks
,
infinity
,
vertexStack
.top(),
paths
))
{
return false;
}
vertexStack
.pop();
}
return true;
}
5 主函数与测试 (Main Method and Testing)
5.1 主函数 (Main Method)
#include "abstract_graph.h"
#include "adjacency_matrix.h"
#include "minimum_spanning_tree.h"
#include "shortest_path.h"
#include "activity_network.h"
#include <string>
#include <vector>
#include <stack>
#include <unordered_map>
#include <iomanip>
#include <iostream>
using namespace std
;
typedef Graphs
::AMVertexNode
<int> AMVertexInt
;
typedef Graphs
::AdjacencyMatrix
<int> AMGraphInt
;
void TestAdjacencyMatrix();
void TestKruskal();
void TestPrim();
void TestDujkstra();
void TestFloyed();
void TestTopologicalSort();
void TestCriticalPath();
int main()
{
TestTopologicalSort();
TestCriticalPath();
system("pause");
return 0;
}
template<class TGraph>
void PrintMatrix(TGraph
& graph
);
void TestTopologicalSort()
{
AMGraphInt
* graph
= new AMGraphInt({ 0, 1, 2, 3, 4, 5 }, true);
graph
->InitializeUndirectedWeights(
{ {0, 1}, {0, 3}, {1, 5}, {2, 1}, {2, 5}, {4, 0}, {4, 1}, {4, 5} },
1.0);
cout
<< "----------拓扑排序 Topological Sort----------" << endl
;
cout
<< "有向图：" << endl
;
cout
<< "邻接矩阵：" << endl
;
PrintMatrix(*graph
);
cout
<< endl
;
std
::vector
<int> paths
;
if (Graphs
::ActivityNetwork
::TopologicalSort(graph
, paths
))
{
cout
<< "拓扑排序：";
for (int i
= 0; i
< paths
.size(); i
++)
{
cout
<< (char)(paths
[i
] + 'A') << "(V" << paths
[i
] << ") ";
}
cout
<< endl
;
}
else
{
cout
<< "拓扑排序失败，有环" << endl
;
}
delete graph
;
cout
<< endl
;
}
void TestCriticalPath()
{
AMGraphInt
* graph
= new AMGraphInt({ 0, 1, 2, 3, 4, 5, 6, 7 }, true);
graph
->InitializeWeights(
{ {0, 1}, {0, 2}, {1, 3}, {2, 3}, {2, 5}, {3, 5}, {3, 4}, {4, 6}, {5, 6}, {6, 7} },
{ 9, 13, 15, 9, 29, 7, 6, 18, 6, 12 });
cout
<< "----------关键路径 Critical Path----------" << endl
;
cout
<< "有向图：" << endl
;
cout
<< "邻接矩阵：" << endl
;
PrintMatrix(*graph
);
cout
<< endl
;
vector
<stack
<int>> paths
;
if (Graphs
::ActivityNetwork
::CriticalPath(graph
, paths
))
{
string str
;
string strAlpha
;
for (int i
= 0; i
< paths
.size(); i
++)
{
str
= "";
strAlpha
= "";
while (!paths
[i
].empty())
{
str
= "v" + to_string(paths
[i
].top()) + " " + str
;
strAlpha
.insert(strAlpha
.begin(), (char)(paths
[i
].top() + 'A'));
paths
[i
].pop();
}
cout
<< "关键路径 " << (i
+ 1) << ": " << str
;
cout
<< " (" << strAlpha
<< ")" << endl
;
}
}
else
{
cout
<< "关键路径失败，有环" << endl
;
}
delete graph
;
cout
<< endl
;
}
4.2 打印结果 (Print Output)
----------拓扑排序 Topological Sort----------
有向图：
邻接矩阵：
A B C D E F
A . 1 . 1 . .
B . . . . . 1
C . 1 . . . 1
D . . . . . .
E 1 1 . . . 1
F . . . . . .
拓扑排序：E(V4) A(V0) D(V3) C(V2) B(V1) F(V5)
----------关键路径 Critical Path----------
有向图：
邻接矩阵：
A B C D E F G H
A . 9 13 . . . . .
B . . . 15 . . . .
C . . . 9 . 29 . .
D . . . . 6 7 . .
E . . . . . . 18 .
F . . . . . . 6 .
G . . . . . . . 12
H . . . . . . . .
关键路径 1: v0 v1 v3 v4 v6 v7 (ABDEGH)
关键路径 2: v0 v2 v5 v6 v7 (ACFGH)
请按任意键继续. . .
