温习Algs4 (四):有向图, 拓扑排序和强连通分量

痛定思痛。 2022-04-12 06:09 190阅读 0赞

### 有向图, 拓扑排序和强连通分量 ###

*  有向图
 *   *  Digraph.java
 *  有向环
 *   *  DiCycle.java
 *  深度优先搜索序列
 *   *  DFSOrder.java
 *  拓扑排序
 *   *  Topological.java
 *  强连通分量
 *   *  KosarajuSCC.java

# 有向图 #

有向图的实现和无向图除了 *addEdge()* 以外一模一样, 不过有向图多了一个方法 *reverse()* , 该方法返回这个有向图的逆图 (即将原图的所有边翻转方向), 在下文的强连通分量中会用到.

## Digraph.java ##

/****************************************************************************** * Compilation: javac Digraph.java * Execution: java Digraph * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.Scanner;
    
    public class Digraph { 
        private int vertexCount;
        private int edgeCount;
        private Bag<Integer>[] adj;
    
        Digraph(int v) { 
            vertexCount = v;
            edgeCount = 0;
            adj = (Bag<Integer>[]) new Bag[v];
            for (int i = 0; i < v; i++) { 
                adj[i] = new Bag<Integer>();
            }
        }
    
        Digraph(Scanner scan) { 
            this(scan.nextInt());
            int e = scan.nextInt();
            for (int i = 0; i < e; i++) { 
                int from = scan.nextInt();
                int to = scan.nextInt();
                addEdge(from, to);
            }
        }
    
        public int V() { 
            return vertexCount;
        }
    
        public int E() { 
            return edgeCount;
        }
    
        public void addEdge(int v, int w) { 
            adj[v].add(w);
            edgeCount++;
        }
    
        public Iterable<Integer> adj(int v) { 
            return adj[v];
        }
    
        public String toString() { 
            StringBuilder sb = new StringBuilder();
            sb.append("<digraph>\n");
            for (int i = 0; i < vertexCount; i++) { 
                for (int j : adj[i]) { 
                    if (j >= i) { 
                        sb.append(" " + i + " -> " + j + "\n");
                    }
                }
            }
            sb.append("</digraph>");
            return sb.toString();
        }
    
        public Digraph reverse() { 
            Digraph g = new Digraph(vertexCount);
            for (int i = 0; i < vertexCount; i++) { 
                for (int j : adj[i]) { 
                    g.addEdge(j, i);
                }
            }
            return g;
        }
    }

# 有向环 #

查找图中所有的环的算法比较复杂, 我将另起一篇博客介绍, 现在介绍的算法是用来检查有向图中**是否**含有环, 这个算法的意义是判断一个有向图是否是有向无环图 (Directed Acyclic Graph, *DAG*).

## DiCycle.java ##

/****************************************************************************** * Compilation: javac DiCycle.java * Execution: java DiCycle * Author: Chenghao Wang ******************************************************************************/
    
    import java.util.NoSuchElementException;
    
    public class DiCycle { 
        private Digraph g;
        private boolean[] mark;
        private Stack<Integer> stack;
        private Bag<Integer> cycle;
        private boolean[] onStack;
    
        DiCycle() {  }
        DiCycle(Digraph g) { 
            this.g = g;
            mark = new boolean[g.V()];
            stack = new Stack<Integer>();
            onStack = new boolean[g.V()];
    
            for (int i = 0; i < g.V(); i++) { 
                if (mark[i]) continue;
                dfs(i);
            }
        }
    
        private void dfs(int i) { 
            mark[i] = true;
            onStack[i] = true;
            stack.push(i);
            for (int next : g.adj(i)) { 
                if (cycle != null) return;
                if (!mark[next]) { 
                    dfs(next);
                }
                else if (onStack[next]) { 
                    cycle = new Bag<Integer>();
                    for (int v : stack) { 
                        cycle.add(v);
                        if (v == next) return;
                    }
                }
            }
            stack.pop();
            onStack[i] = false;
        }
    
        public boolean hasCycle() { 
            return cycle != null;
        }
    
        public Iterable<Integer> aCycle() { 
            if (cycle == null) throw new NoSuchElementException();
            return cycle;
        }
    }

# 深度优先搜索序列 #

当使用深度优先搜索遍历一个 (有向) 图时, 我们能够得到一个遍历节点的序列, 其中有**3**种序列最为典型, 分别是:

1.  先序序列 (preOrder): A, B, D, C 即深度优先搜索的调用顺序
2.  后序序列 (postOrder): D, B, C, A 即深度优先搜索的返回顺序
3.  逆后序序列 (reversePostOrder): A, C, B, D 即把后序序列倒过来的顺序

## DFSOrder.java ##

/****************************************************************************** * Compilation: javac DFSOrder.java * Execution: java DFSOrder * Author: Chenghao Wang ******************************************************************************/
    
    public class DFSOrder { 
        private Digraph g;
        private boolean[] mark;
        private Bag<Integer> reversePostOrder;
        private Queue<Integer> preOrder;
        private Queue<Integer> postOrder;
    
        DFSOrder() {  }
        DFSOrder(Digraph g) { 
            this.g = g;
            mark = new boolean[g.V()];
            reversePostOrder = new Bag<Integer>();
            preOrder = new Queue<Integer>();
            postOrder = new Queue<Integer>();
    
            for (int i = 0; i < g.V(); i++) { 
                if (mark[i]) continue;
                dfs(i);
            }
        }
    
        private void dfs(int i) { 
            mark[i] = true;
            preOrder.enqueue(i);
    
            for (int next : g.adj(i)) { 
                if (mark[next]) continue;
                dfs(next);
            }
    
            postOrder.enqueue(i);
            reversePostOrder.add(i);
        }
    
        public Iterable<Integer> preOrder() { 
            return preOrder;
        }
    
        public Iterable<Integer> postOrder() { 
            return postOrder;
        }
    
        public Iterable<Integer> reversePostOrder() { 
            return reversePostOrder;
        }
    }

# 拓扑排序 #

拓扑排序只对DAG有意义, 所以要先判断该有向图是否是DAG, 即判断它是否含有环. **拓扑排序的序列是DAG的逆后序序列.**

## Topological.java ##

/****************************************************************************** * Compilation: javac Topological.java * Execution: java Topological * Author: Chenghao Wang ******************************************************************************/
    
    public class Topological { 
        private Iterable<Integer> order;
    
        Topological() {  }
        Topological(Digraph g) { 
            DiCycle dc = new DiCycle(g);
            if (!dc.hasCycle()) { 
                DFSOrder dfsOrder = new DFSOrder(g);
                order = dfsOrder.reversePostOrder();
            }
        }
    
        public boolean isDAG() { 
            return order != null;
        }
    
        public Iterable<Integer> order() { 
            return order;
        }
    }

# 强连通分量 #

这里介绍的是Kosaraju强连通分量算法, 其步骤为

1.  按照**有向图的逆图的逆后序序列**遍历节点
2.  对未访问的节点进行深度优先搜索
3.  每次搜索中访问的节点属于同一个强连通分量

该算法比较抽象, 我在这里大体解释一下.

1.  假设可以从节点 **v** 通过DFS访问到节点 **w** , 说明从 **v** 到 **w** 存在一条路径 **①** **且在逆图的逆后序序列中 v 在 w 的前面 ②**.
2.  如果要证明 **v** 和 **w** 强连通, 还需要证明从 **w** 到 **v** 存在一条路径.
3.  由 **①** 可知, 在该图的**逆图**中, 存在一条从 **w** 到 **v** 的路径.
4.  **假设从 w 到 v 不存在一条路径, 那么在逆图的逆后序序列中 w 必在 v的前面, 与②矛盾, 因此从 w 到 v 必然存在一条路径 (自己体会一下)**.
5.  综上, **v** 与 **w** 强连通.

## KosarajuSCC.java ##

/****************************************************************************** * Compilation: javac KosarajuSCC.java * Execution: java KosarajuSCC * Author: Chenghao Wang ******************************************************************************/
    
    public class KosarajuSCC { 
        private Digraph g;
        private int currentID;
        private int[] id;
        private boolean[] mark;
        private Vector<Iterable<Integer>> components;
        private Bag<Integer> component;
    
        KosarajuSCC() {  }
        KosarajuSCC(Digraph g) { 
            this.g = g;
            currentID = 0;
            id = new int[g.V()];
            mark = new boolean[g.V()];
            DFSOrder order = new DFSOrder(g.reverse());
            components = new Vector<Iterable<Integer>>();
            for (int v : order.reversePostOrder()) { 
                if (mark[v]) continue;
                component = new Bag<Integer>();
                dfs(v);
                components.add(component);
                currentID++;
            }
        }
    
        private void dfs(int v) { 
            mark[v] = true;
            id[v] = currentID;
            component.add(v);
            for (int w : g.adj(v)) { 
                if (mark[w]) continue;
                dfs(w);
            }
        }
    
        public boolean connected(int v, int w) { 
            return id[v] == id[w];
        }
    
        public int count() { 
            return currentID;
        }
    
        public Iterable<Iterable<Integer>> components() { 
            return components;
        }
    }