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