[[396433]]

本文轉(zhuǎn)載自微信公眾號「貝塔學JAVA」，作者Silently9527。轉(zhuǎn)載本文請聯(lián)系貝塔學JAVA公眾號。

在上篇中我們學習了深度優(yōu)先搜索，知道了如何通過深度優(yōu)先搜索在圖中尋找路徑;本篇我們繼續(xù)一起來學習深度優(yōu)先搜索算法的其他應(yīng)用場景

連通分量

從一幅圖中找出所有的連通分量，這是也是深度優(yōu)先搜索的一個應(yīng)用場景。什么是連通分量?這個定義在之前的文章中已有提到《如何檢測社交網(wǎng)絡(luò)中兩個人是否是朋友關(guān)系(union-find算法)》

在這篇采用的是union-find算法實現(xiàn)的連通性檢查，本篇我們將采用深度優(yōu)先搜索的方式來找出圖中的所有連通分量

連通分量的API定義

public class DepthFirstCC { 
    public DepthFirstCC(Graph graph);  
     
    public boolean connected(int v, int w); //檢查兩個頂點是否連通 
 
    public int count(); //統(tǒng)計連通分量的總數(shù) 
 
    public int id(int v); //頂點v所在連通分量的標識 
} 

連通分量的API實現(xiàn)

與之前一樣沒掃描到一個頂點我們就需要標記這個頂點，所以依然需要定義一個marked[]數(shù)組

為了統(tǒng)計出圖中總共有多少連通分量，所以需要定義一個變量count

為了判斷兩個頂點是否相連，我們需要把相連的頂點對應(yīng)的標識值記錄成相同值，當在調(diào)用connected方法的時候直接取出兩個頂點的標識值比較，如果相同就是連通的，否則就是非連通;

這個的標識值我們使用的是count的值，每個頂點都需要存一個標識值，所以還需要一個ids[]數(shù)組。

public class DepthFirstCC { 
    private boolean marked[]; 
    private int count; 
    private int[] ids; 
 
    public DepthFirstCC(Graph graph) { 
        this.marked = new boolean[graph.V()]; 
        this.ids = new int[graph.V()]; 
 
        for (int v = 0; v < graph.V(); v++) { 
            if (!this.marked[v]) { 
                dfs(graph, v); 
                count++; 
            } 
        } 
    } 
 
    private void dfs(Graph graph, int v) { 
        this.marked[v] = true; 
        this.ids[v] = count; 
        for (int w : graph.adj(v)) { 
            if (!this.marked[w]) { 
                dfs(graph, w); 
            } 
        } 
    } 
 
    public boolean connected(int v, int w) { 
        return id(v) == id(w); 
    } 
 
    public int count() { 
        return count; 
    } 
 
    public int id(int v) { 
        return ids[v]; 
    } 
 
} 

單元測試

構(gòu)造這樣一個圖，連通分量的總數(shù)應(yīng)該是3

@Test 
public void test() { 
    Graph graph = new Graph(10); 
    graph.addEdge(0, 1); 
    graph.addEdge(0, 2); 
    graph.addEdge(0, 5); 
    graph.addEdge(1, 3); 
    graph.addEdge(2, 4); 
    graph.addEdge(4, 3); 
    graph.addEdge(5, 3); 
 
    graph.addEdge(6, 7); 
 
    graph.addEdge(8, 9); 
 
    DepthFirstCC cc = new DepthFirstCC(graph); 
 
    System.out.println(cc.connected(0,5)); 
    System.out.println(cc.connected(1,2)); 
 
    System.out.println(cc.count()); 
} 

基于深度優(yōu)先搜索實現(xiàn)的連通性檢查理論上說要比以前實現(xiàn)的union-find算法更快，因為檢查連通性深度優(yōu)先搜索實現(xiàn)的版本能夠保證在常量時間內(nèi)完成，而union-find算法不行;

但是union-find也有自己的優(yōu)勢: 不需要把完整的構(gòu)造并表示一張圖，更重要的是union-find算法是動態(tài)的添加節(jié)點。

檢查無向圖中是否有環(huán)

為了減小實現(xiàn)的復(fù)雜度，我們假設(shè)圖中不存在自環(huán)和平行邊;

假如從頂點v出發(fā)存在環(huán)，表示從頂點v出發(fā)的連通分量中某個頂點的鄰接頂點是v，那么在搜索的過程中必定會再次遇到頂點v

實現(xiàn)的思路：

1. 標記已經(jīng)搜索過的每個頂點
2. 當遇到了一個已經(jīng)被標記過的頂點，表示已經(jīng)圖中存在環(huán);
3. 由于圖是無向圖，如果v-w相連，那么頂點v中的鄰接表中有w，w鄰接表中也會有v，但是他們沒有構(gòu)成環(huán)，所以需要排除掉該情況。

public class Cycle { 
    private boolean marked[]; 
    private boolean hashCycle; 
 
    public Cycle(Graph graph) { 
        this.marked = new boolean[graph.V()]; 
        for (int s = 0; s < graph.V(); s++) { 
            if (!this.marked[s]) { 
                dfs(graph, s, s); 
            } 
        } 
    } 
 
    private void dfs(Graph graph, int v, int pV) { 
        this.marked[v] = true; 
        for (int w : graph.adj(v)) { 
            if (!this.marked[w]) { 
                this.dfs(graph, w, v); 
            } else if (w != pV) { 
                this.hashCycle = true; 
                return; 
            } 
        } 
    } 
 
    public boolean hasCycle() { 
        return hashCycle; 
    } 
} 

方法dfs的參數(shù)v表示需要待搜索的頂點，pV表示的是到達v的頂點，所以如果v的鄰接表中有個頂點已被標記過并且該頂點不等于到達v的頂點，那么表示圖中有環(huán)

檢查無向圖是否是二分圖

何為二分圖? 圖中每條邊所連接的頂點都屬于不同的部分;如下圖：

其中紅色節(jié)點表示一個集合，白色節(jié)點是另一個集合，每條邊連接的兩個頂點屬于不同的集合;

舉個實際的例子就很好理解，電影與演員的關(guān)系，電影作為一個頂點，演員作為一個頂點，電影與電影直接是不會有邊，演員與演員直接也不會有邊，這就是一張二分圖。

public class TwoColorGraph { 
    private boolean twoColor = true; 
    private boolean[] marked; 
    private boolean[] color; 
 
    public TwoColorGraph(Graph graph) { 
        this.marked = new boolean[graph.V()]; 
        this.color = new boolean[graph.V()]; 
 
        for (int v = 0; v < graph.V(); v++) { 
            if (!this.marked[v]) { 
                dfs(graph, v); 
            } 
        } 
    } 
 
    private void dfs(Graph graph, int v) { 
        this.marked[v] = true; 
        for (int w : graph.adj(v)) { 
            if (!this.marked[w]) { 
                this.color[w] = !this.color[v]; 
                dfs(graph, w); 
            } else if (this.color[w] == this.color[v]) { 
                this.twoColor = false; 
                return; 
            } 
        } 
    } 
 
    public boolean isTwoColor() { 
        return twoColor; 
    } 
} 

文中所有源碼已放入到了github倉庫:https://github.com/silently9527/JavaCore