数据结构与算法--拓补排序及无环加权有向图的最短路径

现实生活中一些项目工程、生产开发，都有一个所谓的流程。一个流程分为若干个活动或者说步骤，这些活动具有一个优先级，很显然我们得按照优先级顺序去执行它们（优先级相同的活动可以不强调先后），即某些活动完成之后才能执行下一活动。不能把后期的任务放到前面来做是吧。这可以抽象成有向图，且要求该有向图不能成环。比如你参加校园话剧表演，你总得先写剧本 -> 不断排练 -> 登台正式表演。成有向环就是说，正式表演 -> 写剧本，哦？你是啥准备都没就即兴表演了，剧本都是表演后才写，这明显不符合逻辑，所以流程中不允许出现环。如果某个工程中出现了有向环，无疑是设计失误了。

拓补序列

上面表达的意思用图（Graph）来说就是：有向图G中，从顶点v 到w有一条路径，则在顶点序列中v必须在w之前，这样的顶点序列称为拓补序列。而拓补排序就是构造拓补序列的过程。

当且仅当一幅有向图是无环图时它才能进行拓补排序。

拓补排序的核心思想：入度为0的顶点需优先被放入序列中，待所有顶点都被放入，拓补序列就完成了。如果将顶点想像成活动，入度为0就是说任何其他活动执行完毕后也不会轮到该活动了（因为流程图中没有一个箭头指向这个活动），该活动就被漏下、被遗忘了，工程中少了一个步骤那怎么行？！所以对于入度为0的活动，一定要先做；当然如果有多个这样的活动存在，任意选出一个先执行都可以。

基于DFS的顶点排序

基于上述思想，可以使用深度优先搜索实现拓补排序。原理是利用了递归产生的由系统维护的栈。方法调用表示进栈，方法结束表示出栈。进栈的顺序表示了访问顶点的顺序。比如先调用dfs(s)，然后递归调用dfs(w)，再调用dfs(v)，这就表示了一条s -> w -> v的路径。使用DFS保存顶点有三种顺序：

• 前序：在递归调用刚开始将顶点存入队列；
• 后序：在递归调用即将结束时将顶点存入队列；
• 逆后序：在递归调用即将结束时将顶点存入压入栈。

先给出结论：一幅有向无环图的拓补顺序即为所有顶点的逆后序排列。

现在来证明，我们知道拓补序列中对于图中任意边v -> w，v必须在排在w之前。现对于任意v -> w边，当调用dfs(v)时候，无非以下几种情况

• dfs(w)还没被调用。这说明刚进入dfs(v)方法，还没有(即将)进入dfs(w)。那么dfs(w)会在dfs(v)之前返回。
• dfs(w)被调用过了，且已经返回。这说明说明是先dfs(v)，然后dfs(w)，然后dfs(w)执行完毕，当然是返回到dfs(v)方法体了。此时dfs(w)依然是先于dfs(v)返回。
• dfs(w)被调用，但是没有返回。这说明dfs(w)先被调用，然后才调用的dfs(v)，只有这样才会出现dfs(w)调用了却没有返回。方法的调用顺序说明说明之前访问的路径为w -> v，而现在是v -> w的边刚好形成环。这说明在无环有向图中，这最后一种情况不存在。

前两种都是dfs(w)比dfs(v)先返回，所以当处理无环有向图时一定是先返回w再返回v，所以我们利用dfs返回顺序的不变性，在它即将返回之际，用栈存入就一定能保证v -> w的正确顶点排列顺序。既然对于任意边都能保证正确的顶点排列顺序，那么对整个图的所有顶点，排列顺序也是正确的。

开始实现，首先不能有环，写个类判断。

package Chap7;

import java.util.LinkedList;

public class DiCycle {
    private boolean[] marked;
    private int[] edgeTo;
    private boolean[] onStack;
    private LinkedList<Integer> cycle;

    public DiCycle(DiGraph<?> graph) {
        marked = new boolean[graph.vertexNum()];
        edgeTo = new int[graph.vertexNum()];
        onStack = new boolean[graph.vertexNum()];
        // 有向图可能不是强连通的，所以需要从每个顶点出发，寻找有向环
        for (int i = 0; i < graph.vertexNum(); i++) {
            dfs(graph, i);
        }
    }

    public DiCycle(EdgeWeightedDiGraph<?> graph) {
        marked = new boolean[graph.vertexNum()];
        edgeTo = new int[graph.vertexNum()];
        onStack = new boolean[graph.vertexNum()];
        // 有向图可能不是强连通的，所以需要从每个顶点出发，寻找有向环
        for (int i = 0; i < graph.vertexNum(); i++) {
            dfs(graph, i);
        }
    }

    private void dfs(DiGraph<?> graph, int v) {
        // 模拟系统递归使用的栈，方法开始进栈；方法结束出栈
        onStack[v] = true;
        marked[v] = true;
        for (int w : graph.adj(v)) {
            // 如果已经存在环，终止递归方法
            if (hasCycle()) {
                return;
            }
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(graph, w);
                // v -> w的路径，且w在栈中，说明形成有向环
            } else if (onStack[w]) {
                cycle = new LinkedList<>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycle.push(x);
                }
                // 导致成环的连个顶点入栈
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    private void dfs(EdgeWeightedDiGraph<?> graph, int v) {
        // 模拟系统递归使用的栈，方法开始进栈；方法结束出栈
        onStack[v] = true;
        marked[v] = true;
        for (DiEdge edge : graph.adj(v)) {
            // 如果已经存在环，终止递归方法
            if (hasCycle()) {
                return;
            }
            int w = edge.to();
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(graph, w);
                // v -> w的路径，且w在栈中，说明形成有向环
            } else if (onStack[w]) {
                cycle = new LinkedList<>();
                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实现，原理也是递归产生的由系统维护的栈。onStack[]其实就是一条路径，onStack[w] = true说明顶点w位于从起点s可达的onStack[]这条路径中。当找到一条v -> w，而此时w正好在onStack[]中（曾访问过且还在路径中），说明在这条路径上成环了。

然后是深度优先搜索的顶点排序，只是在dfs代码的基础上加了几行添加数据而已。针对拓补排序，我们只需要逆后序排列reversePost。

package Chap7;

import java.util.LinkedList;
import java.util.Queue;

public class DFSorder {
    private boolean[] marked;

    private Queue<Integer> pre; // 前序
    private Queue<Integer> post; // 后序
    private LinkedList<Integer> reversePost; // 逆后序

    public DFSorder(DiGraph<?> graph) {
        pre = new LinkedList<>();
        post = new LinkedList<>();
        reversePost = new LinkedList<>();
        marked = new boolean[graph.vertexNum()];
        // 有向图可能不是强连通的，所以需要从每个顶点出发，寻找有向环
        for (int v = 0; v < graph.vertexNum(); v++) {
            if (!marked[v]) {
                dfs(graph, v);
            }
        }
    }

    public DFSorder(EdgeWeightedDiGraph<?> graph) {
        pre = new LinkedList<>();
        post = new LinkedList<>();
        reversePost = new LinkedList<>();
        marked = new boolean[graph.vertexNum()];
        // 有向图可能不是强连通的，所以需要从每个顶点出发，寻找有向环
        for (int v = 0; v < graph.vertexNum(); v++) {
            if (!marked[v]) {
                dfs(graph, v);
            }
        }
    }

    private void dfs(EdgeWeightedDiGraph<?> graph, int v) {
        pre.offer(v);
        marked[v] = true;

        for (DiEdge edge : graph.adj(v)) {
            int w = edge.to();
            if (!marked[w]) {
                dfs(graph, w);
            }
        }

        post.offer(v);
        reversePost.push(v);
    }

    private void dfs(DiGraph<?> graph, int v) {
        pre.offer(v);
        marked[v] = true;

        for (int w:graph.adj(v)) {
            if (!marked[w]) {
                dfs(graph, w);
            }
        }

        post.offer(v);
        reversePost.push(v);
    }

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

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

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

有了这些，实现拓补排序就轻松的。

package Chap7;

public class TopoSort {
    private Iterable<Integer> order;

    public TopoSort(DiGraph<?> graph) {
        DiCycle cycleFinder = new DiCycle(graph);
        if (!cycleFinder.hasCycle()) {
            DFSorder dfs = new DFSorder(graph);
            order = dfs.reversePost();
        }
    }

    public TopoSort(EdgeWeightedDiGraph<?> graph) {
        DiCycle cycleFinder = new DiCycle(graph);
        if (!cycleFinder.hasCycle()) {
            DFSorder dfs = new DFSorder(graph);
            order = dfs.reversePost();
        }
    }

    public boolean isDAG() {
        return order != null;
    }

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

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 5}, {0, 6}, {2, 0}, {2, 3}, {3, 5},{5, 4},{6, 4}, {6, 9}, {7, 6},
                {8, 7}, {9, 10}, {9, 11}, {9, 12}, {11, 12}};
        DiGraph<?> graph = new DiGraph<>(13, edges);
        TopoSort topo = new TopoSort(graph);

        if (topo.isDAG()) {
            System.out.println(topo.order());
        }
    }
}

/* Output
[8, 7, 2, 3, 0, 6, 9, 11, 12, 10, 5, 4, 1]
*/

先使用DiCycle类判断无环才进入后续操作，然后直接返回了DFS的逆后序排列，就是拓补序列了。isDAG()判断该图是否是一幅无环有向图，如果是，用order方法可以将拓补序列返回。以上几个类我们都重载了相应的方法，使得它们也可以处理加权有向图。

更为流行的实现

如果认为上面的实现不太好懂，将要介绍的这个思路更加直观容易理解，而且更为流行。我们把这句入度为0的顶点必须先被放入序列中，翻译成代码就OK了。

为此我们需要两条队列，一条zeroInQueue专门存放那些入度为0的顶点，另一条队列order表示拓补序列，我们要做的就是每次将前者中的顶点出列，然后入列到后者中。还需要一个in[]数组，存放下标对应顶点的入度。当将一个入度为0的顶点v删除并加入序列中，就表明此活动v已经执行完毕了，从v可达的所有邻接点w，它们入度都要减小1，表示活动w的前期活动已经完成一项（前期活动都完成后才轮到w执行）。若某个顶点的入度在自减过程中变为0，说明它可以被执行了，所以加入到序列中。

好了，给出实现。

package Chap7;

import java.util.LinkedList;
import java.util.Queue;

public class Topological {
    private int[] in;
    private Queue<Integer> zeroInQueue; // 入度为0的队列
    private Queue<Integer> order; // 保存拓补排序的队列

    public Topological(DiGraph<?> graph) {
        zeroInQueue = new LinkedList<>();
        order = new LinkedList<>();
        in = new int[graph.vertexNum()];
        // 原图的逆向图，求逆向图的出度得到的就是原图的入度
        DiGraph<?> R = graph.reverse();
        for (int i = 0; i < graph.vertexNum(); i++) {
            int inCount = 0;
            // 逆向图的出度就是原图的入度
            for (int ignored : R.adj(i)) {
                inCount++;
            }
            // 得到各个顶点的入度数组
            in[i] = inCount;
        }
        // 以上是初始化

        // 先将入度为0的所有顶点入列
        for (int i = 0; i < in.length; i++) {
            if (in[i] == 0) {
                zeroInQueue.offer(i);
            }
        }
        // 不断取出队列中的顶点，将该顶点的邻接点的入度减去1
        while (!zeroInQueue.isEmpty()) {
            int v = zeroInQueue.poll();
            order.offer(v); // 加入到拓补序列中
            // 可以看作是移除该顶点，于是和该顶点相邻的边也删掉。从度的角度来看就是邻接点入度减小1
            for (int w : graph.adj(v)) {
                if (--in[w] == 0) {
                    zeroInQueue.offer(w);
                }
            }
        }
    }

    public Iterable<Integer> order() {
        // 是拓补序列才输出
        if (isDAG()) {
            return order;
        }
        return null;
    }

    public boolean isDAG() {
        // in.length就是图的顶点数，只要不是全部顶点都进入到了拓补排序队列中，说明遇到了有向环
        return order.size() == in.length;
    }

    public static void main(String[] args) {
        int[][] edges = {{0, 1}, {0, 5}, {0, 6}, {2, 0}, {2, 3}, {3, 5},{5, 4},{6, 4}, {6, 9}, {7, 6}, {8, 7}, {9, 10}, {9, 11}, {9, 12}, {11, 12}};
        DiGraph<?> graph = new DiGraph<>(13, edges);
        Topological topo = new Topological(graph);
        System.out.println(topo.order());
    }
}
/*
[2, 8, 0, 3, 7, 1, 5, 6, 4, 9, 10, 11, 12]
*/

由于我实现的有向图的邻接表表示的出度，我很懒..也不想再去实现可以表示入度的邻接表...幸而有向图中我实现了一个可以返回原图的逆向图的方法，而逆向图的出度就是原图的入度。逆向图的生成，代码如下

public DiGraph<Item> reverse() {
    DiGraph<Item> R = new DiGraph<>(vertexNum);
    for (int v = 0; v < vertexNum; v++) {
        for (int w: adj(v)) {
        R.addEdge(w, v);
        }
    }
    return R;
}

其实就是把原来v -> w的边变成了w -> v，每条边都反向了，图也变成了逆向图。

DiGraph<?> R = graph.reverse();
for (int i = 0; i < graph.vertexNum(); i++) {
    int inCount = 0;
    // 逆向图的出度就是原图的入度
    for (int ignored : R.adj(i)) {
        inCount++;
    }
    // 得到各个顶点的入度数组
    in[i] = inCount;
}

逆向图每个顶点的邻接表长度，表示逆向图中该顶点的出度，也就是原图中该顶点的入度了。经过上面几行in[i]现在表示顶点i的入度。

首先将入度本来就为0的那些顶点入列，之后不断出列，不断将那些入度变为0的顶点入列....如此直到队列为空。

然后是判断一个图是否是无环有向图，如果一个图存在有向环，这个环上的所有顶点因为其入度都不为0，导致这些顶点无法加入到队列中，因此序列order中也不会有它们。所以，图中若有顶点没能被存入order，说明存在有向环；如果图中所有顶点都存入order，说明这是幅无环有向图，拓补序列构造成功。

来看几幅图加深对该算法的理解。

首先了解到，图中使用了栈来存放那些入度为0的顶点，而在我们的实现中使用的是队列。这没什么影响，只是最后得到的不是同一个拓补序列。可见，一幅无环有向图可以对应对个拓补序列。因为优先级相同的活动，随便先执行哪个都是一样的，所以会有多个拓补序列。

好，接上图开始，v0、v1、v3是本身入度就为0的顶点，先入栈。接着v3出栈（如果使用队列就是v0出列），从v3可达的v2和v13入度都要减小1，从图中看出来就是从v3引出的所有边都删除了。

然后v1出列，从v1可达的v4、v5、v11入度都减小1。由v1引出的所有边都删除。此时出现了新的入度为0的顶点，即顶点2，压入栈。

之后v2出栈....如此直到栈空。

无环加权有向图的最短路径

使用拓补排序可以很简单地求得无环加权有向图的最短路径，该算法比Dijkstra算法还要快，不过要求有向图一定得是无环的。它的特点有：

• 能在线性时间内解决单点最短路径问题；
• 可以处理负权值的边；
• 还能解决最长路径的问题。

先看拓补排序在最短路径上的应用，只需按照拓补序列依次放松每个顶点，就能解决无环加权有向图的单点最短路径问题。

首先每条边v -> w都只会被放松一次，当v被放松时候，总有distTo[w] <= distTo[v] + e.weight()，该不等式在算法结束之前都成立。因此distTo[w]只会变小。而distTo[v]是不会变化了，因为按照拓补顺序放松顶点，在v被放松后没有任何指向v的边了。正因为如此，实现中也无需marked[]了，因为放松v后没有边指向它，意味着不可能再次访问到这个顶点。

package Chap7;

import java.util.LinkedList;

public class AcycliSP {
    private DiEdge[] edgeTo;
    private double[] distTo;

    public AcycliSP(EdgeWeightedDiGraph<?> graph, int s) {
        edgeTo = new DiEdge[graph.vertexNum()];
        distTo = new double[graph.vertexNum()];

        for (int i = 0; i < graph.vertexNum(); i++) {
            distTo[i] = Double.POSITIVE_INFINITY; // 1.0 / 0.0为INFINITY
        }

        distTo[s] = 0.0;
        // 以上是初始化
        TopoSort topo = new TopoSort(graph);

        if (!topo.isDAG()) {
            throw new RuntimeException("该图存在有向环，本算法无法处理！");
        }
        // 按照拓补顺序依次放松每个顶点，每条边都会被放松一次
        for (int v : topo.order()) {
            relax(graph, v);
        }
    }

    private void relax(EdgeWeightedDiGraph<?> graph, int v) {
        for (DiEdge edge : graph.adj(v)) {
            int w = edge.to();
            if (distTo[v] + edge.weight() < distTo[w]) {
                distTo[w] = distTo[v] + edge.weight();
                edgeTo[w] = edge;
            }
        }
    }

    public double distTo(int v) {
        return distTo[v];
    }

    public boolean hasPathTo(int v) {
        return distTo[v] != Double.POSITIVE_INFINITY;
    }

    public Iterable<DiEdge> pathTo(int v) {
        if (hasPathTo(v)) {
            LinkedList<DiEdge> path = new LinkedList<>();
            for (DiEdge edge = edgeTo[v]; edge != null; edge = edgeTo[edge.from()]) {
                path.push(edge);
            }
            return path;
        }
        return null;
    }

    public static void main(String[] args) {
        int[][] edges = {{5, 4}, {4, 7}, {5, 7}, {5, 1}, {4, 0}, {0, 2},
                {3, 7}, {1, 3}, {7, 2}, {6, 2}, {3, 6}, {6, 0}, {6, 4}};

        double[] weight = {0.35, 0.37, 0.28, 0.32, 0.38, 0.26, 0.39, 0.29,
                0.34, 0.40, 0.52, 0.58, 0.93};

        EdgeWeightedDiGraph<String> graph = new EdgeWeightedDiGraph<>(8, edges, weight);
        AcycliSP acycliSP = new AcycliSP(graph, 5);
            for (int i = 0; i < graph.vertexNum(); i++) {
                System.out.print(5 + " to " + i + ": ");
                System.out.print("(" + acycliSP.distTo(i) + ") ");
                System.out.println(acycliSP.pathTo(i));
            }
            System.out.println();

    }
}

/*
5 to 0: (0.73) [(5->4 0.35), (4->0 0.38)]
5 to 1: (0.32) [(5->1 0.32)]
5 to 2: (0.6200000000000001) [(5->7 0.28), (7->2 0.34)]
5 to 3: (0.61) [(5->1 0.32), (1->3 0.29)]
5 to 4: (0.35) [(5->4 0.35)]
5 to 5: (0.0) []
5 to 6: (1.13) [(5->1 0.32), (1->3 0.29), (3->6 0.52)]
5 to 7: (0.28) [(5->7 0.28)]
*/

by @sunhaiyu

2017.9.27