算法(第四版) 第四章圖4.2

第四章 圖

4.2 有向圖

在有向圖中，邊是單邊的：每條邊所連接的兩個頂點都是一個有序?qū)?，他們的鄰接性是單向的?/p>

4.2.1 術(shù)語

一幅有方向性的圖(或有向圖)是由一組頂點和一組有方向的邊組成的，每條有方向的邊都連接著有序的一對頂點。

在一幅有向圖中，有向路徑由一系列頂點組成，對于其中的每個頂點都存在一條有向邊從它指向序列的下一個頂點。

有向環(huán)為一條至少含有一條邊且起點和終點相同的有向路徑。

簡單有向環(huán)是一條(除了起點和終點必須相同之外)不含有重復(fù)的頂點和邊的環(huán)。

我們假設(shè)有向路徑都是簡單的，除非我們明確指出了某個重復(fù)了的頂點。

4.2.2有向圖的數(shù)據(jù)類型

image-20200728142732938.png

4.2.2.1 有向圖的表示

我們使用鄰接表來表示有向圖，其中邊v->w表示為頂點v所對應(yīng)的鄰接鏈表包含一個w頂點。

4.2.2.2 有向圖取反

API中添加了一個方法reverse()。它返回有向圖的一個副本，但將其中所有邊的方向反轉(zhuǎn)。

Digraph數(shù)據(jù)類型

image-20200728143254924.png

代碼：

public class Digraph {
    private final int V;
    private int E;
    private Bag<Integer>[] adj;

    public Digraph(int V) {
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new Bag<>();
        }
    }

    public int getE() {
        return E;
    }

    public int getV() {
        return V;
    }

    public void addEdge(int v, int w) {
        adj[v].add(w);
        E++;
    }

    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    public Digraph reverse() {
        Digraph R = new Digraph(V);
        for (int v = 0; v < V; v++) {
            for (int w : adj[v])
                R.addEdge(w, v);
        }
        return R;
    }

    public String toString() {
        String s = V + " vertices," + E + " edges\n";
        for (int v = 0; v < V; v++) {
            s += v + ": ";
            for (int w : this.adj(v)) {
                s += w + " ";
            }
            s += "\n";
        }
        return s;
    }
}

4.2.3有向圖的可達(dá)性

單點可達(dá)性。給定一幅有向圖和一個起點s，回答"是否存在一條從s到給定頂點v的有向路徑？"等類似問題。

image-20200728143621652.png

在添加了一個接受多個頂點的構(gòu)造函數(shù)之后，這份API使得用力能夠解決一個更加一般的問題。

多點可達(dá)性。給定一幅有向圖和頂點的集合，回答“是否存在一條從集合中的任意頂點到達(dá)給定頂點v 的有向路徑？”等類似問題。

算法：有向圖的可達(dá)性

public class DirectedDFS {
    private boolean[] marked;

    public DirectedDFS(Digraph g, Integer s) {
        marked = new boolean[g.getV()];
        dfs(g, s);
    }

    public DirectedDFS(Digraph g, Iterable<Integer> sources) {
        marked = new boolean[g.getV()];
        for (int s : sources) {
            dfs(g, s);
        }
    }

    private void dfs(Digraph g, int v) {
        marked[v] = true;
        for (int w : g.adj(v)) {
            if (!marked[w])
                dfs(g, w);
        }
    }

    public boolean marked(int v) {
        return marked[v];
    }
}

4.2.3.2 有向圖的尋路

DepthFirstPaths和BreadthFirstPaths是有向圖處理的重要代碼。它們可以高效地解決以下問題。

單點有向路徑。給定一幅有向圖和一個起點s，回答“從s到給定目的頂點v是否存在一條有向路徑？如果有，找出這條路徑”等類似問題

單點最短有向路徑。給定一幅有向圖和一個起點s，回答“從s到給定目的頂點v是否存在一條有向路徑？如果有找到其中最短的那條（所含邊數(shù)最少）”等類似問題。

/**
 * 有向圖的深度優(yōu)先搜索路徑
 */
class DepthFirstDirectedPaths {
    private boolean[] marked;   //標(biāo)記是否被訪問過
    private int[] edgeTo;           //一直頂點的路徑上的最后一個頂點
    private final int s;        //起點

    public DepthFirstDirectedPaths(Digraph g, int s) {
        this.s = s;
        marked = new boolean[g.getV()];
        edgeTo = new int[g.getV()];
        dfs(g, s);
    }

    private void dfs(Digraph g, int v) {
        marked[v] = true;
        for (int w : g.adj(v)) {
            if (!marked[v]) {
                edgeTo[w] = v;
                dfs(g, w);
            }
        }
    }

    private boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> stack = new Stack<>();
        for (int x = v; v != s; x = edgeTo[x]) {
            stack.push(x);
        }
        stack.push(s);
        return stack;

    }
}

/**
 * 有向圖的廣度優(yōu)先搜索路徑
 */
class BreadthFirstDirectedPaths {
    private boolean[] marked;   //標(biāo)記是否被訪問過
    private int[] edgeTo;           //一直頂點的路徑上的最后一個頂點
    private final int s;        //起點

    public BreadthFirstDirectedPaths(Digraph g, int s) {
        this.s = s;
        marked = new boolean[g.getV()];
        edgeTo = new int[g.getV()];
        bfs(g, s);
    }

    private void bfs(Digraph g, int v) {
        marked[v] = true;
        Deque<Integer> stack = new ArrayDeque<>();
        stack.offer(v);
        while (!stack.isEmpty()) {
            int t = stack.poll();
            for (int w : g.adj(t)) {
                if (!marked[w]) {
                    marked[w] = true;
                    edgeTo[w] = t;
                    stack.offer(w);
                }
            }
        }
    }

    private boolean hasPathTo(int v) {
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> stack = new Stack<>();
        for (int x = v; v != s; x = edgeTo[x]) {
            stack.push(x);
        }
        stack.push(s);
        return stack;

    }
}

4.2.4環(huán)和有向無環(huán)圖

從原則上來說，一幅有向圖可能含有大量的環(huán)；在實際應(yīng)用中，我們一般只會重點關(guān)注其中一小部分，或者只是想知道它們是否存在

尋找有向環(huán)

基于深度優(yōu)先搜索的來解決這個問題并不困難，系統(tǒng)維護(hù)的遞歸調(diào)用的棧正是“當(dāng)前”正在遍歷的有向路徑。一旦我們找到了一條有向邊v->w且w已經(jīng)存在于棧中，就找到了一個環(huán)，因為棧表示的是一條由w到v的有向路徑，而v->w正好補(bǔ)全了這個環(huán)。同時，如果沒有找到這樣的邊，說明有向圖是無環(huán)的。

image-20200728145850797.png
/**
 * 尋找有向環(huán)
 * 如果存在多個有向環(huán),則只找到一個有向環(huán)
 */
public class DirectedCycle {
    private boolean[] marked;
    private int[] edgeTo;
    private Stack<Integer> cycle;   //有向環(huán)中的所有頂點
    private boolean[] onStack;      //遞歸調(diào)用的棧上的所有頂點

    public DirectedCycle(Digraph g) {
        marked = new boolean[g.getV()];
        edgeTo = new int[g.getV()];
        onStack = new boolean[g.getV()];

        for (int v = 0; v < g.getV(); v++) {
            if (!marked[v])
                dfs(g, v);
        }
    }

    private void dfs(Digraph g, int v) {
        marked[v] = true;
        onStack[v] = true;
        for (int w : g.adj(v)) {
            if (hasCycle()) return;
            else if (!marked[w]) {
                edgeTo[w] = v;
                dfs(g, w);
            } else if (onStack[w]) {
                cycle = new Stack<Integer>();
                for (int x = v; x != w; x = edgeTo[w]) {
                    cycle.push(x);
                }
                cycle.push(w);
                cycle.push(v);
            }
        }
        onStack[v] = false;
    }

    public boolean hasCycle() {
        return cycle != null;
    }

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

該類為標(biāo)準(zhǔn)的遞歸bfs()方法添加了一個布爾類型的數(shù)組onStack[]來保存遞歸調(diào)用期間棧上的所有頂點。當(dāng)它找到一條邊v->w且w在棧中的時候，就找到了一個有向環(huán)。環(huán)上的所有頂點可以通過edgeTo[]來得到。

同樣，需要指出的是，廣度優(yōu)先搜索也可以找到是否有環(huán)，這個問題我們放到后面拓?fù)渑判虻臅r候用例題討論。

4.2.4.3 頂點的深度優(yōu)先次序與拓?fù)渑判?/h4>
image-20200728151416010.png

實際上我們已經(jīng)見過一種拓?fù)渑判虻乃惴ǎ褐灰砑右恍写a，深度標(biāo)準(zhǔn)優(yōu)先搜索程序就能完成這項任務(wù)。

如果將dfs()的參數(shù)頂點保存在一個數(shù)據(jù)結(jié)構(gòu)中，遍歷這個數(shù)據(jù)結(jié)構(gòu)實際上就能訪問圖中的所有頂點，遍歷的順序取決于這個數(shù)據(jù)結(jié)構(gòu)的性質(zhì)以及是在遞歸調(diào)用之前還是之后保存。典型的應(yīng)用中，人們感興趣的是頂點的以下3中排列順序。

  • 前序：在遞歸調(diào)用之前將頂點加入隊列。
  • 后序：在遞歸調(diào)用之后將頂點加入隊列。
  • 逆后序：在遞歸調(diào)用之后將頂點壓入棧。
image-20200728151759690.png

有向圖中基于深度優(yōu)先搜索的頂點排序

public class DepthFirstOrder {
    private boolean[] marked;
    private Queue<Integer> pre; //所有頂點的前序排列
    private Queue<Integer> post;    //所有頂點的后序排列
    private Stack<Integer> reversePost; //所有頂點的逆后序排列

    public DepthFirstOrder(Digraph g) {
        marked = new boolean[g.getV()];
        pre = new ArrayDeque<>();
        post = new ArrayDeque<>();
        reversePost = new Stack<>();
        for (int v = 0; v < g.getV(); v++) {
            if (!marked[v]) dfs(g, v);
        }
    }

    private void dfs(Digraph g, int v) {
        marked[v] = true;
        pre.add(v);
        for (int w : g.adj(v)) {
            if (!marked[w])
                dfs(g, w);
        }
        post.add(v);
        reversePost.push(v);
    }

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

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

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

拓?fù)渑判?/strong>

public class Topological {
    private Iterable<Integer> order;    //頂點的拓?fù)渑判?
    public Topological(Digraph g) {
        DirectedCycle cycleFinder = new DirectedCycle(g);
        if (!cycleFinder.hasCycle()) {
          //先判斷是否有環(huán)，有環(huán)的話不能進(jìn)行拓?fù)渑判?            DepthFirstOrder dfs = new DepthFirstOrder(g);
            order = dfs.reversePost();
        }
    }

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

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


一副有向圖的拓?fù)漤樞蚣礊樗许旤c的逆后序排列。
證明。對于任意邊v->w，在調(diào)用dfs(v)的時候，有以下三種情況必成立
        1.dfs(w)已經(jīng)被調(diào)用過且已經(jīng)返回了(w已經(jīng)被標(biāo)記)
        2.dfs(w)還沒有被調(diào)用過(w還未被標(biāo)記)，因此v->w會直接或間接調(diào)用并返回dfs(w),且dfs(w)會在dfs(v)返回前返回。
        3.dfs(w)已經(jīng)調(diào)用還未被返回。證明的關(guān)鍵在于，在有向無環(huán)圖中這種情況是不可能的，由于遞歸調(diào)用鏈意味著存在從w到v的路徑，但存在v->w表示存在一個環(huán)。
        
        在兩種可能的情況中，dfs(w)都會在dfs(v)之前完成，因此在后序排列中w在v之前而在逆后序中v在w之前。因此任意一條邊v->w都如我們所愿地從排名較前頂點指向排名較后的頂點。

在實際應(yīng)用中，拓?fù)渑判蚝陀邢颦h(huán)的檢測總會在一起出現(xiàn)，因為有向環(huán)的檢測是排序的前提。

實際應(yīng)用一下

LeetCode題目:

4.2.5有向圖的強(qiáng)連通性

定義。如果兩個頂點v和w是互相可達(dá)的，則稱它們?yōu)?strong>強(qiáng)連通的。也就是說，既存在一條從v到w的有向路徑，也存在一條從w到v的有向路徑。如果一幅有向圖的任意兩個頂點都是強(qiáng)連通的，則稱這幅有向圖也是強(qiáng)連通的。

4.2.5.1強(qiáng)連通分量

image-20200728153628642.png

Kosaraju算法

算法完成了以下幾點：

  • 在給定的一幅有向圖G中，使用DepthFirstOrder來計算它的反向圖GR的逆后序排列。
  • 在G中進(jìn)行標(biāo)準(zhǔn)的深度優(yōu)先搜索，但是要按照剛才得到的順序而非標(biāo)準(zhǔn)的順序來訪問所有未被標(biāo)記的頂點。
  • 在構(gòu)造函數(shù)中，所有在同一個遞歸dfs()調(diào)用訪問道德頂點都在同一個強(qiáng)連通分量中
public class KosarajuSCC {
    private boolean[] marked;   //已經(jīng)訪問過的頂點
    private int[] id;           //強(qiáng)連通分量的標(biāo)識符
    private int count;  //強(qiáng)連通分量個數(shù)

    public KosarajuSCC(Digraph digraph) {
        marked = new boolean[digraph.getV()];
        id = new int[digraph.getV()];
        DepthFirstOrder order = new DepthFirstOrder(digraph.reverse());
        for(int v:order.reversePost())
        {
            if(!marked[v])
                dfs(digraph,v);
        }
    }

    private void dfs(Digraph digraph, int s) {
        marked[s] = true;
        id[s] = count;
        for (int w : digraph.adj(s)) {
            if (!marked[w])
                dfs(digraph, w);
        }
    }

    public int getCount() {
        return count;
    }

    public boolean stronglyConnected(int v, int w) {
        return id[v] == id[w];
    }
}


命題。使用深度優(yōu)先搜索查找給定有向圖G的反向圖GR，根據(jù)由此得到的所有頂點的逆后序再次使用深度優(yōu)先搜索處理有向圖，其構(gòu)造函數(shù)每次遞歸調(diào)用所標(biāo)記的頂點都在同一個強(qiáng)連通分量中。
證明。首先用反證法證明“每個和s強(qiáng)連通的頂點v都會在構(gòu)造函數(shù)調(diào)用的dfs(G,s)中訪問到”。假設(shè)有一個和s強(qiáng)連通的頂點v不會在構(gòu)造函數(shù)調(diào)用的dfs(G,s)中訪問到。因為存在從s到v的路徑，所以v肯定在之前就已經(jīng)被標(biāo)記過了。但是，因為也存在從v到s的路徑，在dfs(G,v)調(diào)用中s肯定會被標(biāo)記，因此構(gòu)造函數(shù)不會調(diào)用dfs(G,s),矛盾。
    其次，證明“構(gòu)造函數(shù)調(diào)用的dfs(G,s)所到達(dá)的任意頂點v都必然和s強(qiáng)連通“。
設(shè)v為dfs(G,s)到達(dá)的某個頂點。那么,G必然存在一條s到v的路徑，只需要證明G中還存在一條從v到s的路徑即可。這也等價于GR中存在一條從s到v的路徑，只需要證明在GR中存在一條從s到v的路徑即可。
證明的核心在于，按照逆后序進(jìn)行深度優(yōu)先搜索與為這，在GR中進(jìn)行的深度優(yōu)先搜索中，dfs(G,v)必然在dfs(G,s)之前就已經(jīng)結(jié)束了，這樣dfs(G,v)的調(diào)用出現(xiàn)兩種情況
    1.調(diào)用在dfs(G,s)調(diào)用之前（并且在dfs(G,s)）調(diào)用之前結(jié)束
    2.調(diào)用在dfs(G,s)調(diào)用之后（并且在dfs(G,s)）調(diào)用之前結(jié)束
    第一種情況是不可能出現(xiàn)的，因為在GR中存在一條從v到s的路徑；而第二種情況說明GR中存在一條從s到v的路徑。
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容