图论——拓扑排序

阅读此篇之前，需要了解图论的基础知识。

拓扑排序可以解决我们有优先级限制下的任务调度问题中的排序问题，或是类似Java中类的继承关系。

先来看下概念：

拓扑排序：给定一个有向图，将所有的顶点排序，使得所有的有向边均从排在前面的元素指向排在后面的元素。（或是说明无法做到这一点）

通常在进行任务调度类问题需要3步走：

1. 指明任务和优先级。（确定顶点和有向边）
2. 不断检测并去除有向图中的所有环，以确保存在可执行的方案。（构建有向图，检测环）
3. 使用拓扑排序解决问题。（拓扑排序）

有向图的构建，已经在图论的基础知识中详细阐述了，接下来就是如何解决环的问题。

有向环

如果任务x必须在y之前完成，y必须在z之前完成，z必须在x之前完成，出现了有向环，那么这个问题就是无解的。

检测有向环

通过深度优先搜索DFS可以很简单的完成这个检测。

当我们进行DFS时，维护的递归调用栈表示的是系统正在遍历的有向路径，一旦我们找到了一条路径v -> w已经存在于栈中，那么我们就找到了一个环。

相较于有向图而言，使用一个boolean数组onStack[]来保存遍历过的路径，作为检测依据。并用一个Stack来保存环。

DirectedCycle 有向环的检测DirectedCycle.java

public class DirectedCycle {
    private boolean[] marked;
    private int[] edgeTo;
    private Stack<Integer> cycle;   //有向环中的所有顶点（如果存在）
    private boolean[] onStack;      //递归调用的栈上的所有顶点

    public DirectedCycle(Digraph G) {
        onStack = new boolean[G.V()];
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        for (int v = 0; v < G.V(); v++)
            if (!marked[v])
                dfs(G, v);
    }

    private void dfs(Digraph G, int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (hasCycle()) return;
            else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G, w);
            } else if (onStack[w]) {
                cycle = new Stack<>();
                for (int x = v; x != w; x = edgeTo[x])
                    cycle.push(x);
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return cycle != null;
    }

    public Iterable<Integer> cycle() {
        return cycle;
    }
}

拓扑排序数据结构

基于DFS的逆后序排序

拓扑排序所需要的顶点顺序，其实只需要将DFS算法每次访问的顶点（DFS递归访问时，每个顶点只访问一次）采取逆后序排序即可。（压入栈中）

原理：对于v -> w，在进行DFS时递归访问，总是dsf(w)先于dsf(v)完成，故将完成dfs()访问一个顶点时压入栈即可完成v -> w顺序。

DepthFirstOrder 基于DFS的逆后序排序DepthFirstOrder.java

public class DepthFirstOrder {
    ···
    private Stack<Integer> reversePost; //所有顶点的逆后序排列(stack)

    private void dfs(Digraph G, int v) {
        ···
        reversePost.push(v);
    }

    public Iterable<Integer> reversePost() {
        return reversePost;
    }
}

拓扑排序实现

非常简单，就是检测环，如果是有向无环图DAG，则返回顶点逆后序排序即可。

Topological 拓扑排序Topological.java

public class Topological {
    private Iterable<Integer> order;        //顶点的拓扑排序,为所有顶点的逆后序排列。

    public Topological(Digraph G) {
        DirectedCycle cycleFinder = new DirectedCycle(G);
        if (!cycleFinder.hasCycle()) {
            DepthFirstOrder dfs = new DepthFirstOrder(G);
            order = dfs.reversePost();
        }
    }

    public Iterable<Integer> order() {
        return order;
    }
}

性能：

• 时间：和V+E成正比

这是由于每次拓扑排序时，会进行两次DFS。

第一次DFS遍历有向图确保无环，此时V+E。第二次DFS产生逆后序排序，此时V+E。两次都访问了顶点和边，故与V+E成正比。

强连通分量

探寻两点之间是否互相可达，是有向图中的另一个重要部分——强连通分量。

应用

这是一种非常重要的抽象，可以理解为几个相互关联的部分（顶点）是否是一种类型的。比如程序员对于程序模块的划分、写书的作者对于话题或者书中知识点的分类、生物学食物链中的能量流动是否存在相互关系、巨型互联网中网页网站的分模块处理等等。

实现

想实现一个平方级的算法并不难，但是对于大型数据而言是不可接受的（大型稀疏图）。
这里介绍一个Kosaraju算法巧妙的实现。

• 给定的有向图G，使用DepthFirstOrder来计算G的反向图Gr的逆后序排列，得到order。
• 在G的构造函数中DFS，但是DFS访问的顶点顺序根据order进行。

实现简单，但是理解比较难。

命题：用Kosaraju算法处理G，其构造函数中的每次递归都在同一个强连通分量中。
证明：

1. 首先证明每个和s强连通的顶点v都会在构造函数dfs(G,s)中访问到。（这个不难理解，反证法即可）
2. 再证明v和s必然是强连通的。设v为dfs(G,s)中到达的某个顶点，那么G中必然存在s到v的路径。故只要证明存在v到s的路径即可。等价于证明Gr中存在s到v的路径。其中Gr中已经含有v到s的路径，故对Gr进行DFS时，dfs(G,v)必然先于dfs(G,s)结束，并且是在dfs(G,s)之后调用的，这个顺序是由DFS的递归访问导致的。所以此时说明了存在一条s到v的路径。

KosarajuSCC 检测强连通分量KosarajuSCC.java

public class KosarajuSCC {
    private boolean[] marked;
    private int[] id;
    private int count;

    public KosarajuSCC(Digraph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        DepthFirstOrder order = new DepthFirstOrder(G);
        for (int s : order.reversePost()) {
            if (!marked[s]) {
                dfs(G, s);
                count++;
            }
        }
    }

    private void dfs(Digraph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v))
            if (!marked[w])
                dfs(G, w);
    }

    public boolean stronglyConnected(int v, int w) {
        return id[v] == id[w];
    }
    ···
}

其中有向图的反转实现如下：

Digraph 有向图反转Digraph.java

public class Digraph {
    ···
    public Digraph reverse() {
        Digraph R = new Digraph(V);
        for (int v = 0; v < V; v++)
            for (int w : adj[v])
                R.addEdge(w, v);
        return R;
    }
    ···
}

性能：

预处理

• 空间：与V+E成正比
• 时间：与V+E成正比

查询

• 时间：线性

---

参考文献：《算法导论》 《Algorithms, 4th Edition》