溫習Algs4 (四):有向圖, 拓撲排序和強連通分量

有向圖, 拓撲排序和強連通分量

• 有向圖
• • 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;
    }
}