引入
看到“拓扑排序”四个大字，有些人可能以为这是一种类似于快速排序、归并排序的数组排序算法，还有人可能以为这是拓扑学里的深奥知识。今天，我们就仔细聊聊这个在图论中频频出现的算法。
首先是来自百度百科的定义：
对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边 <u,v>∈E(G) ，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。
根据这个定义，我们可以直观地理解拓扑序列为：一个给定图的全部顶点按某种顺序排成的序列，每个顶点出现且只出现一次，且对于图中的任意一条有向边从顶点 A 指向顶点 B ，那么在序列中顶点 A 一定出现在顶点 B 的前面。而拓扑排序也就是从给定的图的所有边中提取出该图的某一个拓扑序列的过程。
比如下面图中的操作就是从图中提取拓扑序列的过程，也即拓扑排序：
#### 拓扑序列有什么性质？ 根据上面的定义，对于图中的所有有向边 A->B（表示A指向B，下同），放入拓扑序列后 A 一定出现在 B 的前面，这就说明，拓扑序列的第一个顶点一定不是某一条边的“终点”，否则该边的“起点”就一定出现在这个顶点前面。
特殊地，如果一个顶点是“孤立点”，也即没有任何一条有向边的“起点”或“终点”是这个点，那么该点在拓扑序列中可以出现在任何一个位置。
如何进行拓扑排序？
根据拓扑序列的性质，第一个顶点一定不是某一条边的“终点”，也即该顶点的入度为0。同样地，所有入度为0的点都可以作为拓扑序列的第一个顶点，所以，我们第一步可以将所有入度为0的点按照任意顺序放入拓扑序列。
我们不妨假设图中存在 A、B 两点，且有一条有向边 A->B，并且没有任何其他有向边的“终点”是顶点 B，那么我们将顶点 A 放入拓扑序列后，就可以随时将顶点 B 放入拓扑序列，因为此时一定满足 A 出现在 B 的前面。同理，假设有两条有向边 A->B, C->B，那么我们将顶点 A、C 都放入拓扑序列后，就可以随时将顶点 B 放入拓扑序列。换句话说，当所有给顶点 B 的入度做出贡献的点都放入拓扑序列后，顶点 B 也就随时可以放入拓扑序列。
那么，我们不妨每次将一个顶点放入拓扑序列后，都将所有以该顶点为“起点”的有向边遍历一遍，将这些边“终点”的入度减1，若某一个“终点”的入度减为0后，说明该点的“限制”被取消了，该点就可以放入拓扑序列。我们反复进行这样的操作对给定图进行“拆分”，直到所有顶点都进入到拓扑序列之中。就完成了「拓扑排序」。
翻译成算法的语言是这样的：
（1）将所有入度为0的点入队；
（2）输出一个入度为0的点；
（3）将与该弧头指向的所有点的入度-1，若入度减至0，则将此点入队，重复（2）和（3）直至队空。
这是它的伪代码：
queue<int> q // 维护队列模拟拓扑排序过程
q <- 所有入度为 0 的点
while(!q.empty()) {
t <- q.front(), q.pop() // 取出队头顶点
枚举所有起点为 t 的边 t -> j {
删掉 t -> j 边，j 的入度减 1
if(j 的入度为 0) {
q <- j // 放入拓扑序列
}
}
}#### 剪刀石头布的必胜秘诀？ 大家都玩过「剪刀石头布」游戏。在这个游戏中，无论我们出什么手势，胜利和失败的几率相等，不存在一种手势是稳赢，也不存在一种手势是稳输，这是因为，“剪刀”、“石头”、“布”三种手势是「循环克制」的，当我们用各种手势克制关系构建一张图后，有如下关系：
我们发现，将“克制关系”看作“有向边”后，剪刀石头布三种手势构成了一个「环」，每一个顶点（也即三种手势）的入度均为 1，所以无法对其进行拓扑排序。这就说明，并不是所有的有向图都有对应的拓扑序列，都可以进行拓扑排序，「只有有向无环图才可以进行拓扑排序」。说到这里，也就引申出了拓扑排序的另一个应用，也即「判断图中是否有环」。
