拓扑排序，是一种听上去很高级的算法，但其实它是很简单的（就基础算法而言）。

本文主要介绍一下拓扑排序最基本的概念和实现过程。（也就是说是一篇入门文章，大佬们可以不用看了）

什么是拓扑排序？

在生活中和数学题中，我们常常会遇到需要完成很多件事的情况比如写很多作业，这些事件之间各有先后顺序，即你必须先完成这件事，才能完成另外的事，我们可以根据这些事来画张图（只是个例子）：

在这张图中，每条有向边代表要想完成 v，就必须完成 u，比如要想打开洛谷，就必须先打开电脑废话。

能不能给这些事排个序，让我按照这个顺序来做事不会冲突呢（比如不会出现先水犇犇再打开洛谷的情况）？

当然可以，我们可以看出，按照ABCDEFGH这个顺序做事就不会冲突。

说了这么多，究竟什么是拓扑排序呢？相信你也看出来了，拓扑排序就是对一张图进行排序，使得每一条路径的起点永远出现在终点的前面，也就是安排一个顺序，使得做事不会冲突。最后的这个顺序，就被称为是拓扑序列，而得出这个序列的过程被称为拓扑排序。

当然，一张图的拓扑序列可能不止一种，比如在上图中BACEDGFH也是一个拓扑序列。

对于要进行排序的图，它必须是一个 DAG（有向无环图），即不会出现要做 A，先做 B，但要做 B，又要先做 A 的情况。

算法思路

拓扑排序其实很简单，对于一个点，如果它没有父亲（即与其相连的入边的起点）或是其父亲都被排在序列里了，那么这个点就可以放进序列，因为它既然没有先决条件，就是可以做的。

概括一下，不断地去做那些没有先决条件或是先决条件被满足的事情，最后所有事情都会做完这句话不适用于我的作业（满足是 DAG 的情况下）。

那么怎么判断一个点有无先决条件呢？很简单，我们在建图时就统计好每个点的入度，入度为00就说明没有先决条件，就是可以做的，在排序时，每做完一件事，就删掉这个点，同时其出边相连的点入度减11，如果一个点的先决条件都被满足了，那么它的入度也就为00了。

**注意：**不是真的要在图里把这个结点删去，而是只用将其相邻的点入度减11就行了，这样就和删去这个点效果是一样的了。

拓扑排序主要有两种实现方法，可以分别类比为 BFS 和 DFS（因为真的很像啊！），我个人比较喜欢用 BFS，因为要开的数组较少。

BFS

这种方法的思路是：每找到一个入度为00的点，就将其入队，然后拓展与其相连的点，将这些点入度减11，因为当前这个点入度为00，所以我们要完成它，完成了它之后，与它相连的点都少了一个先决条件，所以入度减11（这 TM 跟 BFS 有什么区别？）。

这里我们就不用开一个 visit 数组来记录到没到达过了，因为既然一个点入度都为00了，怎么可能还有路径到达它呢？所以不需要。

由于太简单，我就不手动模拟了，就是和 BFS 一模一样的。

PS：由于没有拓扑排序的模板题，所以我就自己出了一道。

输入格式：

第11行两个整数nn和mm，表示在这张图中共有nn个点，mm条边。

第22行到第m+1m+1行，每行两个数uu和vv，表示从uu到vv有一条边。

输入保证没有环。

输出格式：

输出共一行，为这个图的拓扑序列，每两个数字之间一个空格。

输入数据：

1
2
3
4
5
6
7
8
9
10
11
12
8 11
1 3
2 3
1 5
2 5
3 4
4 6
4 7
5 6
5 7
6 8
7 8

输出数据：

答案不唯一！

1
1 2 3 4 5 6 7 8

不用看了就是上面那张图

参考代码：

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
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
	int next;
	int to;
};
Edge edge[100001];//静态链式前向星存图
int n,m,cnt,tot,head[10001],in[10001],ans[10001];//in 记录每个点的入度，ans 存答案
queue<int> q;//我比较喜欢用 STL，如果不会的可以百度一下，很简单的，几分钟就会了
void add_edge(int u,int v)
{
	cnt++;
	edge[cnt].next=head[u];
	edge[cnt].to=v;
	head[u]=cnt;
}
void topo()
{
	for(int i=1;i<=n;i++)
		if(!in[i])
			q.push(i);//一开始检测哪些点入度为 0，从这些点开始干♂。
	while(!q.empty())//如果队列不为空
	{
		int u=q.front();//取出队头元素
		q.pop();//队头元素出队
		ans[++tot]=u;//因为这个点被放进队列，有且只有一种情况，即它的入度为 0，这种情况下我们当然是可以来做这件事的
		for(int i=head[u];i;i=edge[i].next)//枚举与这个点相连的所有点。
		{
			int v=edge[i].to;
			in[v]--;//这些点的入度减 1
			if(!in[v])//如果这个点入度为 0 了，就可以入队了，没有必要枚举完了再判断哪些点入度为 0
				q.push(v);
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add_edge(a,b);
        in[b]++;
	}
	topo();
	for(int i=1;i<=tot;i++)
		printf("%d ",ans[i]);
	return 0;
}

是不是很简单啊？只要会 BFS 就应该能看懂了。

DFS

这种方法相对来说就要麻烦一些，因为要开一个visitvisit数组，但其实也没麻烦到哪去。

思路：从一个入度为00的点开始遍历，先一直走到底，在回溯的时候，将当前点压入栈中，也就是说，最后的出度为00的点将会最先被压入栈中，也就会最后被输出。同时，我们不再走之前走过的点了，因为这些点已经被压入栈中。

注意！ 要遍历所有点，找到入度为00的点，从这一点开始进行遍历，因为入度为00的点不可能从其他点到达，所以要从每一个初始入度为00的点都遍历一次。

参考代码：（题目如上）

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
#include<bits/stdc++.h>
using namespace std;
struct Edge
{
	int next;
	int to;
};
Edge edge[100001];
int n,m,cnt,tot,head[10001],in[10001],ans[10001],visit[10001];
stack<int> s;//还是 STL 模板
void add_edge(int u,int v)
{
	cnt++;
	edge[cnt].next=head[u];
	edge[cnt].to=v;
	head[u]=cnt;
}
void topo(int u)
{
	visit[u]=1;//标记当前点
	for(int i=head[u];i;i=edge[i].next)//枚举所有出边
	{
		int v=edge[i].to;
		if(!visit[v])
			topo(v);//继续遍历
	}
	s.push(u);//将这一点压入栈
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++)
	{
		int a,b;
		scanf("%d%d",&a,&b);
		add_edge(a,b);
        in[b]++;
	}
	for(int i=1;i<=n;i++)//一定要从每一个入度为 0 的点都遍历一次
		if(!in[i])
			topo(i);
	while(!s.empty())
	{
		printf("%d ",s.top());
		s.pop();
	}
	return 0;
}

很简单是不是啊？

拓扑排序由于保证了每个点、每条边只会被遍历一次，所以其时间复杂度为O(n+m)O(n+m)，还是很不错了。

在最开始，我们曾提到拓扑排序只能处理没有环的图，但其实，它还可以用来判断是否存在环。

思路很简单，如果一张图中存在环，那么我们是不可能将所有的点都放进答案数组里的，组成环的那些点因为入度怎么都不可能为00（试想一下让你在穿裤子之前必须穿上衣，但在穿上衣之前又必须穿裤子，那么最后你一定什么也穿不了），所以它们不会被放进数组。

简单来说，在 BFS 完之后，加一条语句判断tottot是否小于nn，如果是，那么一定存在环。

就像这样：

1
2
if(tot<n)
    printf("有环啊啊啊啊！！！");

这只是用 BFS 的思路，DFS 的你们可以自己想一下，我就不再说了。

总结

emmm……没有什么好总结的了，都很简单，关键是做题（基础算法和题目可是两回事，蒟蒻亲身体验 QAQ）

推荐几道题目吧：

全都是 你谷 上的哦（没办法窝太菜了只有你谷账号没有 CF 和 AT 之类的账号 QAQ）

P4017 最大食物链计数（拓扑排序+动归，极其简单，看题就切）

P1137 旅行计划（简单明了，DFS 一遍就过）

P1038 神经网络（版子题，简单）

P1983 车站分级 （有难度，但主要是在如何建图上，建好了跑一遍拓扑就好了）

P1347 排序（也差不多是版子题，迄今为止做过最简单的一道蓝题）

由于我是个菜鸡，所以这些题保证你只要学懂了拓扑排序都是可以做的，只是有些要稍微思考一下。

如果有哪里不对请大佬在评论里指出，蒟蒻感谢之极 qwq。