数据结构与算法--拓补排序及无环加权有向图的最短路径
现实生活中一些项目工程、生产开发，都有一个所谓的流程。一个流程分为若干个活动或者说步骤，这些活动具有一个优先级，很显然我们得按照优先级顺序去执行它们（优先级相同的活动可以不强调先后），即某些活动完成之后才能执行下一活动。不能把后期的任务放到前面来做是吧。这可以抽象成有向图，且要求该有向图不能成环。比如你参加校园话剧表演，你总得先写剧本 -> 不断排练 -> 登台正式表演。成有向环就是说，正式表演 -> 写剧本，哦？你是啥准备都没就即兴表演了，剧本都是表演后才写，这明显不符合逻辑，所以流程中不允许出现环。如果某个工程中出现了有向环，无疑是设计失误了。
拓补序列
上面表达的意思用图（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 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 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 pre; // 前序 private Queue post; // 后序 private LinkedList 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 pre() { return pre; } public Iterable post() { return post; } public Iterable reversePost() { return reversePost; }} 有了这些，实现拓补排序就轻松的。
package Chap7;public class TopoSort { private Iterable 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 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 zeroInQueue; // 入度为0的队列 private Queue 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 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- reverse() { DiGraph
- 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 pathTo(int v) { if (hasPathTo(v)) { LinkedList 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 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