前提：拓扑排序是对有向无环图来说的，无向图、有环图都不存在拓扑排序。
拓扑排序是将图G中的所有顶点排成一个线性序列，使得对于任意一堆有边顶点<u, v>，在线性序列中，u都出现在v之前。
拓扑排序可以反应某种方案是否是切实可行的。
一般一个图是否是有向图我们分析题意要求就能知道，但是究竟有没有环存在，就不是瞄一眼就能发现的了，所以，虽然拓扑排序是针对有向无环图而言的一种性质，但是反过来，一个有向图是否有拓扑排序，也可以反过来解决该图是否存在环、以及存在多少环等等问题，也就是某种方案可不可行。
接下来我们通过代码学习如何获得一个有向图的拓扑排序：
拓扑排序一定是从入度为0的顶点开始的（假如入度不为0不就是有点要排在它的前面了嘛qwq），所以，我们通过删除点(及由该点出发的所有边)的方法可以不断更新制作拓扑排序时当前图的状态，这样的步骤不断执行，直到图中能删的点(入度为0的点)都删光了，我们的程序就执行到了终点。
我们还是用链式前向星来存储图
使用队列来记录我们的拓扑序列（说是队列不过其实还是个每次只读末尾的数组啦，也没用到queue容器qwq）
寻找拓扑序列样例代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| // 要先用一个数组记录各个顶点最初的入度，这个数组可以在读入边数据的时候进行++记录
int queue[maxn];
int iq = 0; // 表示当前队列长度，起始当然是0啦(懒得iq++也可以直接懒人向量法)
// 先将图里入度为0的顶点加入队列
// 第一层入度为0的点，其顺序就只是存储顺序决定哩，而且不重要(除非想找所有的拓扑排序qwq)
for (int i = 1;i <= n;i++)
if (indegree[i] == 0)
queue[iq++] = i;
// 删点，对队列做更新
for (int i = 0;i < iq;i++) {
// 按队列顺序删点删边(终点的入度--就算删掉这条边了)
for (int k = head[queue[i]];k != 0;k = Edge[k].next) {
indegree[Edge[k].to]--;
if (indegree[Edge[k].to] == 0)
queue[iq++] = Edge[k].to;
}
}
|
这时候我们得到了一个序列，其实这个序列无论如何都能得到（空序列也是序列！），所以接下来需要判断一下是否是拓扑序列，同时也就判断出当前的图是不是有向无环图啦。
判断样例代码：
1
2
3
4
5
6
7
8
9
10
11
12
| cout << "iq=" << iq << " n=" << n << endl;
if (iq == n) {
cout << "有拓扑序列：" << endl;
// 输出拓扑排序序列
for (int i = 0;i < iq;i++)
cout << queue[i] << " ";
cout << endl;
}
else {
cout << "没有拓扑序列" << endl;
}
|
前面的输入样例是个有向有环图，这里添加一组有向无环图的样例用于学习：
graph LR
v1((v1))--5-->v2((v2))
v1((v1))--6-->v3((v3))
v2((v2))--9-->v4((v4))
v3((v3))--10-->v5((v5))
v3((v3))--4-->v6((v6))
v4((v4))--12-->v6((v6))
v5((v5))--6-->v7((v7))
v6((v6))--9-->v7((v7))
v7((v7))--24-->v8((v8))
v6((v6))--3-->v8((v8))
1
2
3
4
5
6
7
8
9
10
11
| 8 10
1 2 5
1 3 6
2 4 9
3 5 10
3 6 4
4 6 12
5 7 6
6 7 9
6 8 3
7 8 24
|
完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
| #include<bits/stdc++.h>
using namespace std;
const long long maxn = 1e5 + 50, maxm = 1e7 + 50;
struct EdgeNode {
int to; // 终点
int w; // 权值
int next; // 下一位置
};
EdgeNode Edge[maxm];
int head[maxn];
int indegree[maxn];
int main() {
int n, m;
cin >> n >> m;
// 初始化head
memset(head, -1, sizeof(head)); // 初始化为0应该也冇问题，反正只是方便我们判断终点啦，想用向量也行qwq
// 读入数据
for (int i = 0;i < m;i++) {
int fi, ti, wi;
cin >> fi >> ti >> wi;
Edge[i].to = ti;
Edge[i].w = wi;
Edge[i].next = head[fi];
head[fi] = i;
// 记录各个顶点的入度(当该点是终点的时候++qwq)
indegree[ti]++;
}
// 要先用一个数组记录各个顶点最初的入度，这个数组可以在读入边数据的时候进行++记录
int queue[maxn];
int iq = 0; // 表示当前队列长度，起始当然是0啦(懒得iq++也可以直接懒人向量法)
// 先将图里入度为0的顶点加入队列
// 第一层入度为0的点，其顺序就只是存储顺序决定哩，而且不重要(除非想找所有的拓扑排序qwq)
for (int i = 1;i <= n;i++)
if (indegree[i] == 0)
queue[iq++] = i;
// 删点，对队列做更新
for (int i = 0;i < iq;i++) {
// 按队列顺序删点删边(终点的入度--就算删掉这条边了)
for (int k = head[queue[i]];k != -1;k = Edge[k].next) {
indegree[Edge[k].to]--;
if (indegree[Edge[k].to] == 0)
queue[iq++] = Edge[k].to;
}
}
// 这里可以判断是否有环啦，假如此时iq的值小于顶点的数量n，不就是说明接下来没法删边了嘛，也就是说最后剩下了环。
cout << "iq=" << iq << " n=" << n << endl;
if (iq == n) {
cout << "有拓扑序列：" << endl;
// 输出拓扑排序序列
for (int i = 0;i < iq;i++)
cout << queue[i] << " ";
cout << endl;
}
else {
cout << "没有拓扑序列" << endl;
}
return 0;
}
|
该算法在O(m)的时间内对indegree数组进行初始化，在O(n)时间内对queue进行初始化，后面的部分虽然看起来是两层循环，但实际上是m条边各遍历一次，所以时间复杂度只有O(m)而已，所以一共也就O(m+n)的复杂度。还是很友好滴。