圖算法系列之深度優(yōu)先搜索（一）

吐血整理程序員必讀書單：https://github.com/silently9527/ProgrammerBooks

微信公眾號(hào)：貝塔學(xué)Java

前言

在上一篇中我們把圖通過鄰接表數(shù)組表示出來了，這個(gè)數(shù)據(jù)結(jié)構(gòu)將會(huì)做我們實(shí)現(xiàn)圖算法的基礎(chǔ)，本篇我們將一起開始學(xué)習(xí)圖算法的第一個(gè)搜索算法 - 深度優(yōu)先搜索

搜索API的定義

public class Search {
    Search(Graph graph, int s);

    boolean marked(int v);
    
    int count();
}

在開始實(shí)現(xiàn)算法之前，我們依然先來定義搜索的API

1. 構(gòu)造方法提供了一個(gè)圖對(duì)象，以及一個(gè)起點(diǎn)s，需要找到與s連通的所有頂點(diǎn)
2. marked判斷頂點(diǎn)s與v是否相鄰
3. count返回與頂點(diǎn)s相連的總頂點(diǎn)數(shù)

深度優(yōu)先搜索

假如上圖是一個(gè)迷宮，我們需要從頂點(diǎn)0開始找到一條出路，假設(shè)我們有一條無限長的繩子，和一支粉筆，那么可以這樣考慮找到出路：

1. 先選擇一條通道走，在走的路上放上一根繩子
2. 每遇到一個(gè)路口就用筆標(biāo)記一下，繼續(xù)選擇一條未走過的通道
3. 當(dāng)遇到一個(gè)已經(jīng)被標(biāo)記的路口時(shí)就退回到上一個(gè)路口繼續(xù)選擇一個(gè)未走過的通道
4. 當(dāng)回退的路口已經(jīng)沒有路可以走的時(shí)候就在繼續(xù)往后回退

這種方式繩子總能幫你找到一條出路，而標(biāo)記不會(huì)讓你重復(fù)走已經(jīng)走過的通道。

深度優(yōu)先搜索的實(shí)現(xiàn)思路就和走迷宮的方式一樣；

public class DepthFirstSearch {
    private boolean marked[]; 
    private int count;

    public DepthFirstSearch(Graph graph, int s) {
        this.marked = new boolean[graph.V()];
        this.dfs(graph, s);
    }

    private void dfs(Graph graph, int v) {
        marked[v] = true;
        count++;
        for (int w : graph.adj(v)) {
            if (!marked[w]) {
                dfs(graph, w);
            }
        }
    }

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

    @Override
    public int count() {
        return count;
    }
}

在搜索一張圖的時(shí)候，使用遞歸來遍歷所有的頂點(diǎn)，在訪問其中一個(gè)頂點(diǎn)時(shí)：

1. 標(biāo)記它被已經(jīng)訪問
2. 遞歸的訪問與之相連的所有鄰接點(diǎn)

單元測試：構(gòu)建下面這張圖，然后測試深度優(yōu)先搜索

@Test
public void test() {
    Graph graph = new Graph(8); //構(gòu)建一張圖
    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); //為了展示

    SeDepthFirstSearcharch search = new DepthFirstSearch(graph, 0);
    System.out.println(search.count());
    System.out.println(search.marked(6));
    System.out.println(search.marked(7));
    System.out.println(search.marked(2));
    System.out.println(search.marked(5));
}

尋找路徑的API

以上的遞歸算法只是一個(gè)開始，從上面的結(jié)果我們可以看出，我們只能判斷出哪些頂點(diǎn)與起點(diǎn)s是連通的，無法給出具體的路徑出來；換句話說，我們需要實(shí)現(xiàn)從頂點(diǎn)s到頂點(diǎn)v是否存在路徑可達(dá)，如果存在請(qǐng)打印出來

public class Paths {
    Paths(Graph graph, int s);
    
    boolean hasPathTo(int v); //判斷出從s->v是否存在路徑
    
    Iterable<Integer> pathTo(int v); //如果存在路徑，返回路徑
}

基于深度優(yōu)先搜索查找圖中的可達(dá)路徑

我們依然基于這張圖來看，由于我們需要找出可達(dá)的路徑，所以我們?cè)谶M(jìn)行搜索的時(shí)候需要記錄下圖中的邊，這里我們使用的是一個(gè)數(shù)組edgeTo[]，如果存在一條邊是v->w，那么可以表示成edgeTo[w]=v，在深度搜索完成之后這個(gè)edgeTo[]數(shù)組就是一顆由父鏈表示的一顆樹 （父鏈樹在之前的文章中也使用過《如何檢測社交網(wǎng)絡(luò)中兩個(gè)人是否是朋友關(guān)系（union-find算法）》）

public class DepthFirstPaths {
    private boolean marked[];
    private int[] edgeTo;
    private int s;

    DepthFirstPaths(Graph graph, int s) {
        this.s = s;
        this.marked = new boolean[graph.V()];
        this.edgeTo = new int[graph.V()];
        this.dfs(graph, s);
    }

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

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

    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) {
            throw new IllegalStateException("s不能到達(dá)v");
        }
        Stack<Integer> stack = new LinkedListStack<>();
        stack.push(v);
        while (edgeTo[v] != s) {
            stack.push(edgeTo[v]);
            v = edgeTo[v];
        }
        stack.push(s);
        return stack;
    }
}

畫圖來詳細(xì)跟蹤深度優(yōu)先搜索的運(yùn)行軌跡，記錄了edgeTo的變化以及父鏈樹的逐漸形成

最終父鏈樹形成了，接下來我們來寫單元測試校驗(yàn)下生成的父鏈樹和實(shí)際的運(yùn)行結(jié)果是否一致

@Test
public void test() {
    Graph graph = new Graph(8);
    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);

    DepthFirstPaths paths = new DepthFirstPaths(graph, 0);
    System.out.println(paths.hasPathTo(5));
    System.out.println(paths.hasPathTo(2));
    System.out.println(paths.hasPathTo(6));

    paths.pathTo(5).forEach(System.out::print);
    System.out.println();
    paths.pathTo(4).forEach(System.out::print);
    System.out.println();
    paths.pathTo(2).forEach(System.out::print);


}

驗(yàn)證結(jié)果完全匹配了父鏈樹

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

最后（點(diǎn)關(guān)注，不迷路）

文中或許會(huì)存在或多或少的不足、錯(cuò)誤之處，有建議或者意見也非常歡迎大家在評(píng)論交流。

最后，寫作不易，請(qǐng)不要白嫖我喲，希望朋友們可以點(diǎn)贊評(píng)論關(guān)注三連，因?yàn)檫@些就是我分享的全部動(dòng)力來源??