一、定义
对一个有向无环图(Directed Acyclic Graph，DAG)G进行拓扑排序，是指将G中所有顶点排成一个线性序列，使得对于图中任意一对顶点u和v，若顶点u排在顶点v前面，则图中不存在v->u的路径。
也就是说：拓扑排序是对有向无环图的顶点的一种排序，它使得如果存在一条从顶点A到顶点B的路径，那么在排序中B一定出现在A的后面。
1-1 一幅DAG的拓扑排序结果
二、基本思想
一副有向无环图的拓扑排序，就是所有顶点的逆后序排列。
所谓顶点的逆后序排序，就是在遍历图的过程中，优先输出入度为0的顶点。
2-1 拓扑排序示意图
三、源码实现
public class Topological {
private boolean[] marked;
private Stack<Integer> postorder; // vertices in postorder
public Topological(Digraph G) {
postorder = new Stack<Integer>();
marked = new boolean[G.V()];
for (int v = 0; v < G.V(); v++) {
if (!marked[v])
dfs(G, v);
}
}
private void dfs(Digraph G, int v) {
marked[v] = true;
for (int w : G.adj(v)) {
if (!marked[w]) {
dfs(G, w);
}
}
postorder.push(v);
}
public Iterable<Integer> reversePost() {
Stack<Integer> reverse = new Stack<Integer>();
for (int v : postorder)
reverse.push(v);
return reverse;
}
}
性能分析
使用DFS对有向无环图进行拓扑排序，需要访问所有顶点和边，所需的时间和V+E成正比。
- 时间复杂度
O(V+E)
