作者：klivitamJ，一個愛好寫作，樂意分享的前端人。
來源：https://www.imooc.com/article/285772
最近又有點學不進去了，不知道是不是天氣熱的緣故哈，沒辦法只好寫一點算法來保持學習的路線不間斷咯。關於BFS和DFS，這是我們在面試的時候經常會遇到的兩個基礎算法，為什麼說基礎呢？因為它理解了之後才10行左右的代碼，你說基礎不基礎？
一、 BFSBFS，全稱：Breadth First Search。中文翻譯為廣度優先搜索或者是寬度優先搜索，具體是怎麼回事兒呢？
首先來用下面一顆的樹來引入一下廣度優先搜索的實現步驟：
我先來從結果分析上面的遍歷結果，我發現廣度優先搜索有這樣的特點對：
通過上面的結果來分析，其實我們很容易發現廣度優先算法有點隊列的意味在裡面。
怎麼理解呢？來看下面一套圖：
通過前面的探究，我們大概曉得了廣度優先搜索的一個大致流程，也差不多知道其實現的規則有點類似於隊列。此時可能有人會說了，你只是講解了一個簡單的樹，而我們看到的BFS一般是用圖來展示的。
針對上面的疑問，我們首先來畫一個無向圖。
其實在我的理解裡面：圖和樹最大的區別就是樹有專門的起點，但是圖卻沒有固定的起點。我們可以從任何一個點做起點來去搜索，例如：從A點出發，搜索結果是：
A->B->C->D->E->F
從E點出發：
E-> C->D->F->A->B
…
這樣，我們其實就可以把之前樹的那一套類似到圖中，只不過圖沒有起點罷了，並且將樹的子層換成了與指定節點相連的節點。這樣類比之下也可以用隊列來實現。具體的代碼如下：
首先我們建立一張圖：
let graph = {
'A':['B','C'],
'B':['A','C','D'],
'C':['A','D','E'],
'D':['B','C','E'],
'E':['C','D','F'],
'F':['E']
}
然後BFS的實現代碼如下：
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
}
好了，前面談到了廣度優先搜索，那麼什麼是深度優先搜索呢？
首先我來用一套圖集來輔助理解深度優先搜索的歷程：
總之，我對於深度優先搜索的理解就是：
這樣看來，深度優先是不是有一點棧的意思在裡面呢？怎麼理解哦，我們再來看下面一套圖。
通過上面的圖級演示是不是很容易就能看出來深度優先搜索的實現原理呢？下面我們用代碼的方式來去演示一下其原理吧：
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
}
說了這麼多，感覺午休的時間都所剩無幾了，感覺自己還是沒有把這部分的內容講清楚。本來想額外寫一點關於廣度優先搜索的更深層次的用法的（作為很多圖形結構的基礎，其實應用還是比較廣的），但我還是需要睡的呀！反正中午看來是說不完了。關於還沒寫完的內容呢，我這裡提及一下：
如果相鄰節點之間的距離相同的情況下，我們想求廣度優先搜索的最短路徑怎麼來求呢？
如果相鄰節點之間的距離不同呢？我們應該如何來計算呢？