【图论】拓扑排序：一个名字高大上的实际很简单的算法（图文详解）

前言

在看到“拓扑序列”这4个字的时候，笔者人是傻的。拓扑序列是啥？听着就感觉好厉害！然后，当我得知“拓扑”两个字其实是一个大家都知道的单词“Top”的音译时，我不禁在想：翻译成这样，估计是故意让大家觉得这个知识点很难的吧。事实证明的确是这样，拓扑排序的概念与实现都是非常简单的。别被看上去高大上的名字吓到了。

拓扑序列概念介绍

首先，我们给出一个如图的有向图

然后我们给出一个序列a={1，2，3，4}，我们随便在有向图中选择一条边，我们都能满足在序列a中，这条边起点的编号一定在终点的编号之前。那么，我们就称为序列a是这个有向图的拓扑序列。

根据拓扑序列的概念，我们能知道：对于某些有向图而言，它的拓扑序列是不唯一的。只要是一个序列满足拓扑序列的定义，我们就可以说这个序列是这张图的拓扑序列。

当然，并不是所有图都是存在拓扑序列的，如果我们发现有向图中存在环，那么无论如何我们也找不出一个序列满足拓扑序列的定义。

如图，我们发现如果在之前的图中加上一条边，那么这张图就没有拓扑序列了。

拓扑序列求法介绍

首先，我们需要复习（预习？）一下离散数学中的知识点，入度。
所谓入度，就是对于有向图中的一个点而言，有多少个箭头是指向它的的。比如在最上方的没有环的有向图中，点1的入度为0，点2与3的入度都为1，点3的入度为2。

在了解了入度后，我们开始进行拓扑排序，在排序中，我们使用的是BFS广度优先搜索的思路进行点的遍历。
0.初始化：建图，求出所有点的入度。
1.我们首先遍历全图要找到入度为0的点，我们在我们的图中首先找到了点1

广度遍历所有以1为起点的边，删除这些边，操作为点2的入度减去1，然后就是这样，我们把点1放进拓扑序列中的最前面，a={1}；

再次循环遍历所有还没有放进序列的点，我们发现图中点2的入度已经变成0了，标记出来重复对点1的操作，a={1，2}

继续遍历，我们找到了点3，操作。a={1，2，3}

最后找到了点4，所有点都操作完毕，a={1，2，3，4}，拓扑排序结束。

没有拓扑序列的有环图判断

之前我们说过，并不是所有的有向图都存在拓扑序列的，那么我们要怎么来进行判断呢？首先，我们放一个存在环的有向图来进行上述的算法

我们对于上述图按照之前的算法进行处理完点1，2后，会变成这样

此时，a={1，2}，按照算法，我们应该在剩下的点中寻找入度为0的点，然后我们发现，找不到了，由于有环的存在，我们已经无法在接下来的图中找到入度为0的点了，算法结束，最后序列a定格在a={1，2}无法继续更新。

如果根据上面的算法判断，程序会认为此时的a就是最后的拓扑序列，但是显然不是。我们发现a中的点的数量为2，小于点的总数5。所以，假如我们求出最后的序列中点的数量少于点的总数，那么我们就知道有向图中存在环，该图不存在拓扑序列。

拓扑排序的代码实现

例题链接：Acwing 有向图的拓扑序列

给定一个 n 个点 m 条边的有向图，点的编号是 1 到 n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出 −1。

若一个由图中所有点构成的序列 A 满足：对于图中的每条边 (x,y)，x 在 A 中都出现在 y 之前，则称 A 是该图的一个拓扑序列。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行，每行包含两个整数 x 和 y，表示存在一条从点 x 到点 y 的有向边 (x,y)。

输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。
否则输出 −1。

数据范围
1≤n,m≤1e5
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

这道题就是一道板子题，所以我们直接贴上代码，不过要看懂代码你需要事先知道以下知识点
1.c++STL中 数据结构queue的基本使用方法
2.链式前向星的存图方法----->链式前向星CSDN博客
3.作者重定义的memset函数（ #define mem(a,b) memset(a,b,sizeof(a)) ）

//#pragma GCC optimize(2)
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<string>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<set>
#include<bitset>
#include<ctime>
#include<cstring>
#include<list>
#define ll long long
#define ull unsigned long long
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
typedef  pair<int, int> PII;
const int N = 1e5 + 7;
int n, m;
int e[N], ne[N], h[N], id = 1;  //链式前向星存图
int rd[N];  //存放每个点的入度
bool ch[N];  //用来判断该点有没有被放进序列中
bool haveans = true;  //用来判断是否有拓扑序列
queue<int>q;  //用来存放拓扑序列的队列

void add(int a, int b)   //加边的函数
{
	e[id] = b;
	ne[id] = h[a];
	h[a] = id++;
	rd[b]++;
}

void topsort()   //拓扑排序实现函数
{
	bool flag = true;  //flag为true就代表还能找到入度为0的点

	while (flag)
	{
		flag = false;  //先改为，找不到入度为0的点

		for (int i = 1; i <= n; i++)
		{
			if (rd[i] == 0&&!ch[i])
			{
				ch[i] = true;   
				flag = true;   //找到了入度为0的点就把flag改为true，继续循环
				q.push(i);   //把入度为0的点放进队列q
				for (int j = h[i]; j != -1; j = ne[j])    //BFS遍历所有以i为起点的边
				{
					int k = e[j];
					rd[k]--;  //每一条边的入度减一，删除该边
				}
			}
		}

	}

}

void solve()
{
	bool flag = true;
	cin >> n >> m;
	mem(h, -1);
	for (int i = 0; i < m; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
	}
	topsort();
	if (q.size() != n)   //如果队列中元素数量不等于点的总数就代表图中有环，没有拓扑序列
		cout << "-1" << endl;
	else   //否则输出拓扑序列
		while (!q.empty())
		{
			cout << q.front();
			q.pop();
			if (!q.empty())
				cout << ' ';
			else
				cout << endl;
		}

}

int main()
{
	//std::ios::sync_with_stdio(false);
	//cin.tie(0), cout.tie(0);
	solve();
	return 0;
}
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
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99

作者：Avalon Demerzel，喜欢我的博客就点个赞吧，更多图论与数据结构知识点请见作者专栏《图论与数据结构》