上次寫(xiě)了篇圖的基本構(gòu)造方法综芥，運(yùn)用圖這種強(qiáng)大的數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)力崇，還能解決實(shí)際應(yīng)用中的許多問(wèn)題爸黄，今天這篇就主要整理一些常見(jiàn)的應(yīng)用

一、路徑問(wèn)題

路徑問(wèn)題在圖的處理領(lǐng)域是非常重要的擎鸠。如我們最常見(jiàn)的走迷宮缀磕，就是典型的尋路問(wèn)題。這里主要運(yùn)用深度優(yōu)先和廣度優(yōu)先算法兩種方式來(lái)進(jìn)行路徑尋找劣光，這2種搜索算法在很多數(shù)據(jù)結(jié)構(gòu)中都有重要的運(yùn)用袜蚕，之前寫(xiě)的一篇二叉查找樹(shù)中的層序遍歷就用到了廣度優(yōu)先算法，這里就詳細(xì)的介紹一下绢涡。

1.深度優(yōu)先尋找路徑

首先是深度優(yōu)先,為了更加形象牲剃，直接看下圖
![][1]

這里以頂點(diǎn)1為出發(fā)點(diǎn)，4為終點(diǎn)雄可。假設(shè)一個(gè)人要走到終點(diǎn)凿傅，從1出發(fā)有三條路徑缠犀，首先沿著往5的路徑進(jìn)行遍歷，依次1 -> 5 -> 9 -> 8狭归，然后發(fā)現(xiàn)沒(méi)路了夭坪，就返回上一頂點(diǎn)，到頂點(diǎn)5這里發(fā)現(xiàn)還有一條路就繼續(xù)沿著這條路走过椎，5->3->6室梅，結(jié)果又沒(méi)路了，就繼續(xù)返回到起點(diǎn)疚宇，沿著另一條路行走......1->2->4亡鼠，一看，這下就直接到終點(diǎn)了敷待，轉(zhuǎn)了幾條路終于找到了終點(diǎn)间涵，那心里真是無(wú)比的興奮啊榜揖！回到正題勾哩，看看這個(gè)具體實(shí)現(xiàn)，可以用一個(gè)boolean類(lèi)型的變量來(lái)標(biāo)記是否遍歷過(guò)該頂點(diǎn)举哟，用一個(gè)int型的變量表示從起點(diǎn)到一個(gè)頂點(diǎn)的已知路徑上的最后一個(gè)頂點(diǎn)思劳。至于圖的基本構(gòu)造可以參考我之前寫(xiě)的[圖論基礎(chǔ)篇][2]

/**
 *  圖的深度優(yōu)先查找路徑
 * @author Legend
 */
public class DepthFirstPaths {

    private boolean[] marked; // 該頂點(diǎn)是否調(diào)用過(guò)dfs
    private int[] edgeTo; // 從起點(diǎn)到一個(gè)頂點(diǎn)的已知路徑上的最后一個(gè)頂點(diǎn)
    private final int s; // 起點(diǎn)
    // 圖的初始化
    public DepthFirstPaths(Graph G,int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G,s);
    }
    // 深度優(yōu)先主方法
    private void dfs(Graph G,int v) {
        marked[v] = true;
        // 遍歷與頂點(diǎn)v相連的邊
        for (int w : G.adj(v)) {  
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(G,w);  // 繼續(xù)遞歸的進(jìn)行遍歷
            }
        }
    }
   // 是否存在s到v的路徑
    public boolean hasPathTo(int v) {
        return marked[v];
    }
   // s到v的路徑
    public Iterable<Integer> PathTo(int v) {
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack<>();
        for (int i = v;i != s;i = edgeTo[i]) {
            path.push(i);
        }
        path.push(s);
        return path;
    }
}

因?yàn)槲覀円獪?zhǔn)確的知道每一條路徑，所以這里創(chuàng)建了一個(gè)edgeTo變量用于記錄從起點(diǎn)到一個(gè)頂點(diǎn)的已知路徑上的最后一個(gè)頂點(diǎn)妨猩，而edgeTo[w] = v表示的就是從w到v的路徑潜叛。再看PathTo方法，首先判斷是否有從s到v的路徑壶硅，沒(méi)有就返回null威兜。然后實(shí)例化一個(gè)Stack類(lèi)型對(duì)象path，依次遍歷庐椒，把路徑上每一個(gè)頂點(diǎn)都push進(jìn)去椒舵，最后在push頂點(diǎn)，并返回path约谈。

2.廣度優(yōu)先尋找路徑

廣度優(yōu)先正如其名笔宿，優(yōu)先進(jìn)行廣度的遍歷，整個(gè)過(guò)程呈擴(kuò)散狀窗宇。這里還是用上面那張圖，為了方便查看特纤，還是把圖片放到這里军俊。
![][3]
[1]: http://img.mukewang.com/59fb24c20001780108340606.png
[2]: http://blog.cspojie.cn/2017/10/20/%E5%9B%BE%E8%AE%BA-%E5%9F%BA%E7%A1%80%E7%AF%87/#more，這里直接用Graph來(lái)表示捧存，然后具體實(shí)現(xiàn)看看下面的代碼
[3]: http://img.mukewang.com/59fd753d0001780108340606.png
還是用之前的情景粪躬，從頂點(diǎn)1出發(fā)担败，先遍歷和1相鄰的頂點(diǎn) 2,5,3，然后從頂點(diǎn)2開(kāi)始镰官，右繼續(xù)遍歷和2相鄰的頂點(diǎn)提前，因?yàn)橐呀?jīng)遍歷過(guò)頂點(diǎn)1，所以這里就只需要遍歷頂點(diǎn)7和頂點(diǎn)4泳唠，發(fā)然后現(xiàn)就直接到終點(diǎn)了狈网，這是在特殊的情況下，如果先遍歷的是另外的頂點(diǎn)笨腥，那么幾乎要走完每條路才能找到終點(diǎn)拓哺。這里就不多說(shuō)了，重點(diǎn)講下具體實(shí)現(xiàn)脖母，這里用一個(gè)抽象數(shù)據(jù)結(jié)構(gòu)---隊(duì)列來(lái)實(shí)現(xiàn)士鸥，首先創(chuàng)建一個(gè)隊(duì)列，然后把起點(diǎn)標(biāo)記后插入隊(duì)列中去谆级，如果隊(duì)列不為空就把當(dāng)前的頂點(diǎn)彈出隊(duì)列烤礁，然后依次遍歷和這個(gè)頂點(diǎn)相鄰的頂點(diǎn)，并把這些頂點(diǎn)標(biāo)記后也加入隊(duì)列肥照，接下來(lái)用同樣的方式將下一頂點(diǎn)彈出隊(duì)列脚仔，遍歷和其相鄰的頂點(diǎn)，直到隊(duì)列為空就停止遍歷建峭。好了玻侥，具體看下面的代碼

/**
 *
 * 廣度優(yōu)先尋找路徑
 * @author Legend
 **/

public class BreadthFirstPaths {

    private boolean[] marked;
    private int[] edgeTo;
    private final int s;
    public BreadthFirstPaths(Graph G,int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        try {
            bfs(G,s);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
    }
    private void bfs(Graph G,int s) throws InterruptedException {
        Queue<Integer> queue = new Queue<Integer>();
        marked[s] = true;
        queue.enqueue(s);
        while ( !queue.isEmpty() ) {
            int v = queue.dequeue(); // 從隊(duì)列中彈出一個(gè)頂點(diǎn)
            for (int w : G.adj(v)) { // 遍歷和該頂點(diǎn)相鄰的頂點(diǎn)
                if ( !marked[w] ) {
                    edgeTo[w] = v; // 保存最短路徑的最后一條邊
                    marked[w] = true; // 標(biāo)記它 因?yàn)樽疃搪窂揭阎?                    queue.enqueue(w);
                }
            }
        }
    }
    public boolean hasPathTo(int v) {
        return marked[v];
    }
    public Iterable<Integer> pathTo(int v) {
        if ( !hasPathTo(v) ) {
            return null;
        }
        Stack<Integer> path = new Stack<>();
        for (int i = 0;i != s;i =edgeTo[i] ){
            path.push(i);
        }
        path.push(s);
        return path;
    }
}

這里同樣運(yùn)用了pathTo方法，頂點(diǎn)與路徑的標(biāo)記過(guò)程和深度優(yōu)先尋找路徑是一樣的亿蒸，這里就不多說(shuō)了凑兰。

連通分量問(wèn)題

1.介紹

連通分量也是一個(gè)比較常見(jiàn)的問(wèn)題，主要用于判斷任意兩個(gè)結(jié)點(diǎn)的連接狀態(tài)边锁，特別是用于檢測(cè)網(wǎng)絡(luò)連接與電路連接的問(wèn)題中姑食，運(yùn)用比較廣。

2.基本實(shí)現(xiàn)

也沒(méi)什么好說(shuō)的茅坛，這里還是運(yùn)用深度優(yōu)先的方法音半，比較簡(jiǎn)單，就直接上代碼

/**
 * 使用深度優(yōu)先找出圖中的連通分量
 *
 * @author Legend
 * @create 2017-11-01 8:23
 **/

public class CC {
    private int count;
    private boolean marked[];
    private int[] id;

    public CC(Graph G) {
        marked = new boolean[G.V()];
        id = new int[G.V()];
        for (int s = 0;s < G.V();s++) {
            if (!marked[s]) {
                dfs(G,s);
                count++;
            }
        }
    }
    private void dfs(Graph G,int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G,w);
            }
        }
    }
    // 判斷兩個(gè)結(jié)點(diǎn)是否相連接
    public boolean isConnected(int v,int w) {
        return id[v] == id[w];
    }
    // v所在連通分量的標(biāo)識(shí)符（0~count-1）
    public int id(int v) {
        return id[v];
    }
    // 連通分量的數(shù)量
    public int count() {
        return count;
    }
}

雙色問(wèn)題

1.介紹

能否用2種顏色將圖的所有頂點(diǎn)著色贡蓖，使得任意一條邊的兩個(gè)端點(diǎn)的顏色都不相同,這個(gè)問(wèn)題也就等價(jià)于當(dāng)前的圖是不是二分圖曹鸠。因?yàn)槎鏄?shù)其實(shí)就是一種比較特殊的圖，所以才有這個(gè)問(wèn)題斥铺。

2.基本實(shí)現(xiàn)

具體實(shí)現(xiàn)可以用一個(gè)bool類(lèi)型的變量來(lái)表示2種顏色彻桃，直接在構(gòu)造方法里面進(jìn)行循環(huán)，這里也是運(yùn)用深度優(yōu)先的方式晾蜘。首先判斷當(dāng)前結(jié)點(diǎn)是否被遍歷邻眷，沒(méi)被遍歷過(guò)就進(jìn)行遍歷眠屎，也就是用bool型變量將其標(biāo)記為true，然后遍歷和這個(gè)結(jié)點(diǎn)相連的結(jié)點(diǎn)肆饶，并且把這個(gè)結(jié)點(diǎn)和相鄰的結(jié)點(diǎn)涂上不同的顏色改衩。然后進(jìn)行判斷
先來(lái)看下代碼

/**
 * 雙色問(wèn)題
 *
 * @author Legend
 * @create 2017-11-01 9:17
 **/

public class TwoColor {
    private boolean[] marked; //當(dāng)前結(jié)點(diǎn)是否被遍歷過(guò)
    private boolean[] color; // 表示不同顏色
    private boolean isTwoColorable = true; // 是否能用2種顏色表示
    public TwoColor(Graph G) {
        marked = new boolean[G.V()];
        color = new boolean[G.V()];
        for (int s = 0;s < G.V();s++) {
            if (!marked[s]) {
                dfs(G,s);
            }
        }
    }
    private void dfs(Graph G,int v) {
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                color[w] = !color[v];
                dfs(G,w);
            } else if (color[w] == color[v]) {
                isTwoColorable = false;
            }
        }
    }
    public boolean isBipartite() {
        return isTwoColorable;
    }
}

如果這2個(gè)頂點(diǎn)顏色相同，則不能使得任意一條邊的2個(gè)端點(diǎn)的顏色都不相同驯镊，則這個(gè)圖不是二分圖葫督，試想一下，如果是二分圖阿宅，任意一條的兩個(gè)端點(diǎn)肯定顏色是不相同的候衍。因?yàn)槊看伪闅v時(shí)都將當(dāng)前頂點(diǎn)與連接頂點(diǎn)標(biāo)記了2種不同的顏色，如果這個(gè)頂點(diǎn)有多個(gè)相鄰頂點(diǎn)洒放，并且這些相鄰頂點(diǎn)又有邊相連蛉鹿，這必然會(huì)造成2個(gè)顏色相同，這樣的圖自然也不可能是二分圖了往湿。

因?yàn)檫@篇博客主要是整理圖論的一些應(yīng)用的問(wèn)題妖异，所以對(duì)于這些問(wèn)題的優(yōu)化這里不是重點(diǎn)，有興趣的可以自己去查查資料领追，那圖論應(yīng)用篇就暫時(shí)到這里了他膳。
ps：該blog首發(fā)lenged's blog