最近又有點(diǎn)學(xué)不進(jìn)去了，不知道是不是天氣熱的緣故哈，沒(méi)辦法只好寫(xiě)一點(diǎn)算法來(lái)保持學(xué)習(xí)的路線不間斷咯。 關(guān)于BFS和DFS，這是我們?cè)诿嬖嚨臅r(shí)候經(jīng)常會(huì)遇到的兩個(gè)基礎(chǔ)算法，為什么說(shuō)基礎(chǔ)呢？因?yàn)樗斫饬酥蟛?0行左右的代碼，你說(shuō)基礎(chǔ)不基礎(chǔ)？

一、 BFS

BFS，全稱：Breadth First Search。中文翻譯為廣度優(yōu)先搜索或者是寬度優(yōu)先搜索，具體是怎么回事兒呢？
首先來(lái)用下面一顆的樹(shù)來(lái)引入一下廣度優(yōu)先搜索的實(shí)現(xiàn)步驟：

我先來(lái)從結(jié)果分析上面的遍歷結(jié)果，我發(fā)現(xiàn)廣度優(yōu)先搜索有這樣的特點(diǎn)對(duì)：

• 先從根節(jié)點(diǎn)處查找，然后一層一層的往下查找。
  怎么理解呢？首先查找A也就是第一層，然后再查找BC，也就是第二層，最后查找DEF 也就是第三層。
• 查找子層的時(shí)候，應(yīng)該按照父層的順序來(lái)查找子層。
  怎么理解呢？首先查找A節(jié)點(diǎn)，然后查找A的子層B和C，當(dāng)然我們?cè)诓檎褹子層的時(shí)候先來(lái)查找的B節(jié)點(diǎn)，那么在查找B的子節(jié)點(diǎn)的時(shí)候就要優(yōu)先查找B的子節(jié)點(diǎn)。同理如果第二層里面先查找C也是一樣。
• 廣度優(yōu)先搜索的搜索結(jié)果并不唯一。

通過(guò)上面的結(jié)果來(lái)分析，其實(shí)我們很容易發(fā)現(xiàn)廣度優(yōu)先算法有點(diǎn)隊(duì)列的意味在里面。
怎么理解呢？來(lái)看下面一套圖：

首先新建一個(gè)隊(duì)列，先去查找一下樹(shù)的根結(jié)點(diǎn)，并且將根結(jié)點(diǎn)A放入隊(duì)列中。

...
依次類推，就將所謂的最后的廣度優(yōu)先搜索的路線給畫(huà)出來(lái)了：

最終結(jié)果

通過(guò)前面的探究，我們大概曉得了廣度優(yōu)先搜索的一個(gè)大致流程，也差不多知道其實(shí)現(xiàn)的規(guī)則有點(diǎn)類似于隊(duì)列。此時(shí)可能有人會(huì)說(shuō)了，你只是講解了一個(gè)簡(jiǎn)單的樹(shù)，而我們看到的BFS一般是用圖來(lái)展示的。
針對(duì)上面的疑問(wèn)，我們首先來(lái)畫(huà)一個(gè)無(wú)向圖。

其實(shí)在我的理解里面：圖和樹(shù)最大的區(qū)別就是樹(shù)有專門(mén)的起點(diǎn)，但是圖卻沒(méi)有固定的起點(diǎn)。我們可以從任何一個(gè)點(diǎn)做起點(diǎn)來(lái)去搜索，例如：從A點(diǎn)出發(fā)，搜索結(jié)果是：
A->B->C->D->E->F
從E點(diǎn)出發(fā)：
E-> C->D->F->A->B
...

這樣，我們其實(shí)就可以把之前樹(shù)的那一套類似到圖中，只不過(guò)圖沒(méi)有起點(diǎn)罷了，并且將樹(shù)的子層換成了與指定節(jié)點(diǎn)相連的節(jié)點(diǎn)。這樣類比之下也可以用隊(duì)列來(lái)實(shí)現(xiàn)。具體的代碼如下：

首先我們建立一張圖：

let graph = {
    'A':['B','C'],
    'B':['A','C','D'],
    'C':['A','B' ,'D','E'],
    'D':['B','C','E'],
    'E':['C','D','F'],
    'F':['E']
}

然后BFS的實(shí)現(xiàn)代碼如下：

function bfs(graph,startPoint){
    let queue = [];
    let result = []

    queue.push(startPoint);
    result.push(startPoint);

    while(queue.length>0){
        let point = queue.shift();
        let nodes = graph[point];
        for(let node of nodes){
            if(result.includes(node)) continue;
            result.push(node);
            stack.push(node);
        }
    }
    return result

}

二、DFS

好了，前面談到了廣度優(yōu)先搜索，那么什么是深度優(yōu)先搜索呢？
首先我來(lái)用一套圖集來(lái)輔助理解深度優(yōu)先搜索的歷程：

首先選定起點(diǎn)為A（起點(diǎn)是任意的），然后從A出發(fā)，搜索到B

然后再?gòu)腂出發(fā)，搜索到C

如果搜索到?jīng)]有可以搜索的節(jié)點(diǎn)，就應(yīng)該回溯到最近存在相鄰可以的節(jié)點(diǎn)處繼續(xù)搜索。

總之，我對(duì)于深度優(yōu)先搜索的理解就是：

• 訪問(wèn)頂點(diǎn)A
• 依次從A的未被訪問(wèn)的鄰接點(diǎn)出發(fā)，對(duì)圖進(jìn)行深度優(yōu)先遍歷；直至圖中和A有路徑相通的頂點(diǎn)都被訪問(wèn)；
• 若此時(shí)圖中尚有頂點(diǎn)未被訪問(wèn)，則從一個(gè)未被訪問(wèn)的頂點(diǎn)出發(fā)，重新進(jìn)行深度優(yōu)先遍歷，直到圖中所有頂點(diǎn)均被訪問(wèn)過(guò)為止。

這樣看來(lái)，深度優(yōu)先是不是有一點(diǎn)棧的意思在里面呢？怎么理解哦，我們?cè)賮?lái)看下面一套圖。

首先我們從A出發(fā)，將節(jié)點(diǎn)A移入棧，然后將A移出棧

將A的子節(jié)點(diǎn)C，B移入棧內(nèi)。

然后將E移出棧，將與E相連的F，D節(jié)點(diǎn)移入棧內(nèi)

通過(guò)上面的圖級(jí)演示是不是很容易就能看出來(lái)深度優(yōu)先搜索的實(shí)現(xiàn)原理呢？下面我們用代碼的方式來(lái)去演示一下其原理吧：

function dfs(graph,startPoint){
    let stack = [];
    let result = []

    stack.push(startPoint);
    result.push(startPoint);

    while(stack.length>0){
        let point = stack.pop();
        let nodes = graph[point];
        for(let node of nodes){
            if(result.includes(node)) continue;
            result.push(node);
            stack.push(node);
        }
        

    }
    return result

}

說(shuō)在最后

說(shuō)了這么多，感覺(jué)午休的時(shí)間都所剩無(wú)幾了，感覺(jué)自己還是沒(méi)有把這部分的內(nèi)容講清楚。本來(lái)想額外寫(xiě)一點(diǎn)關(guān)于廣度優(yōu)先搜索的更深層次的用法的（作為很多圖形結(jié)構(gòu)的基礎(chǔ)，其實(shí)應(yīng)用還是比較廣的），但我還是需要睡的呀！反正中午看來(lái)是說(shuō)不完了。關(guān)于還沒(méi)寫(xiě)完的內(nèi)容呢，我這里提及一下：
如果相鄰節(jié)點(diǎn)之間的距離相同的情況下，我們想求廣度優(yōu)先搜索的最短路徑怎么來(lái)求呢？
如果相鄰節(jié)點(diǎn)之間的距離不同呢？我們應(yīng)該如何來(lái)計(jì)算呢
如果明天中午有機(jī)會(huì)的話，我會(huì)細(xì)細(xì)講解這一塊的內(nèi)容的，敬請(qǐng)期待哦！