拓扑排序

一、定义

对一个有向无环图(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)