介绍

拓扑排序作用在有向无环图（Directed Acyclic Graph,简称DAG）上。

拓扑排序干了这样一件事情：如果图上有一条边 \(u \rightarrow v\)，那么排序后 \(u\) 一定在 \(v\) 前。或说是在不破坏DAG内部的顺序的前提下，将DAG拉直成一条链。

比如说下面的图：

就是一个DAG。它的拓扑排序后的链是：3 4 2 1 5 (答案不唯一)

Kahn算法

Kahn算法用来求解一个DAG的拓扑排序。

步骤

• 首先，先删除所有入度为 \(0\) 的点。如上图，就是 \(3\) 与 \(4\)。

• 重复以上步骤直到图上所有点都被删除，删除的顺序就是拓扑排序的结果。

这个算法用到了一个定理：DAG删点时，整个图仍然是一个DAG。

参考代码如下：

By @totorato

void topo_sort(int lim, int ord[]){
	top = 0;
	int pos = 0;
   for(int i=1; i<=lim; i++)
		if(!ind[i])
			stk[++top] = i;
	while(top){
		int x = stk[top--];
		ord[++pos] = x;
		for(int i=fst[x]; i; i=nxt[i])
		{
			ind[v[i]]--;
			if(!ind[v[i]])
				stk[++top] = v[i];
		}
	}
}

鸣谢

参考资料：

• 算法学习笔记(53): 拓扑排序