圖文詳解 DFS 和 BFS

前言

深度優(yōu)先遍歷（Depth First Search, 簡(jiǎn)稱 DFS） 與廣度優(yōu)先遍歷（Breath First Search）是圖論中兩種非常重要的算法，生產(chǎn)上廣泛用于拓?fù)渑判?，尋路（走迷宮），搜索引擎，爬蟲等，也頻繁出現(xiàn)在 leetcode，高頻面試題中。

本文將會(huì)從以下幾個(gè)方面來(lái)講述深度優(yōu)先遍歷，廣度優(yōu)先遍歷，相信大家看了肯定會(huì)有收獲。

• 深度優(yōu)先遍歷，廣度優(yōu)先遍歷簡(jiǎn)介
• 習(xí)題演練
• DFS，BFS 在搜索引擎中的應(yīng)用

深度優(yōu)先遍歷，廣度優(yōu)先遍歷簡(jiǎn)介

深度優(yōu)先遍歷

深度優(yōu)先遍歷主要思路是從圖中一個(gè)未訪問(wèn)的頂點(diǎn) V 開始，沿著一條路一直走到底，然后從這條路盡頭的節(jié)點(diǎn)回退到上一個(gè)節(jié)點(diǎn)，再?gòu)牧硪粭l路開始走到底...，不斷遞歸重復(fù)此過(guò)程，直到所有的頂點(diǎn)都遍歷完成，它的特點(diǎn)是不撞南墻不回頭，先走完一條路，再換一條路繼續(xù)走。

樹是圖的一種特例（連通無(wú)環(huán)的圖就是樹），接下來(lái)我們來(lái)看看樹用深度優(yōu)先遍歷該怎么遍歷。

1、我們從根節(jié)點(diǎn) 1 開始遍歷，它相鄰的節(jié)點(diǎn)有 2，3，4，先遍歷節(jié)點(diǎn) 2，再遍歷 2 的子節(jié)點(diǎn) 5，然后再遍歷 5 的子節(jié)點(diǎn) 9。

2、上圖中一條路已經(jīng)走到底了（9是葉子節(jié)點(diǎn)，再無(wú)可遍歷的節(jié)點(diǎn)），此時(shí)就從 9 回退到上一個(gè)節(jié)點(diǎn) 5，看下節(jié)點(diǎn) 5 是否還有除 9 以外的節(jié)點(diǎn)，沒(méi)有繼續(xù)回退到 2，2 也沒(méi)有除 5 以外的節(jié)點(diǎn)，回退到 1，1 有除 2 以外的節(jié)點(diǎn) 3，所以從節(jié)點(diǎn) 3 開始進(jìn)行深度優(yōu)先遍歷，如下

3、同理從 10 開始往上回溯到 6, 6 沒(méi)有除 10 以外的子節(jié)點(diǎn)，再往上回溯，發(fā)現(xiàn) 3 有除 6 以外的子點(diǎn) 7，所以此時(shí)會(huì)遍歷 7

3、從 7 往上回溯到 3， 1，發(fā)現(xiàn) 1 還有節(jié)點(diǎn) 4 未遍歷，所以此時(shí)沿著 4， 8 進(jìn)行遍歷,這樣就遍歷完成了

完整的節(jié)點(diǎn)的遍歷順序如下（節(jié)點(diǎn)上的的藍(lán)色數(shù)字代表）

相信大家看到以上的遍歷不難發(fā)現(xiàn)這就是樹的前序遍歷,實(shí)際上不管是前序遍歷，還是中序遍歷，亦或是后序遍歷，都屬于深度優(yōu)先遍歷。

那么深度優(yōu)先遍歷該怎么實(shí)現(xiàn)呢，有遞歸和非遞歸兩種表現(xiàn)形式，接下來(lái)我們以二叉樹為例來(lái)看下如何分別用遞歸和非遞歸來(lái)實(shí)現(xiàn)深度優(yōu)先遍歷。

1、遞歸實(shí)現(xiàn)

遞歸實(shí)現(xiàn)比較簡(jiǎn)單，由于是前序遍歷，所以我們依次遍歷當(dāng)前節(jié)點(diǎn)，左節(jié)點(diǎn)，右節(jié)點(diǎn)即可，對(duì)于左右節(jié)點(diǎn)來(lái)說(shuō)，依次遍歷它們的左右節(jié)點(diǎn)即可，依此不斷遞歸下去，直到葉節(jié)點(diǎn)（遞歸終止條件），代碼如下

public?class?Solution?{
????private?static?class?Node?{
????????/**
?????????*?節(jié)點(diǎn)值
?????????*/
????????public?int?value;
????????/**
?????????*?左節(jié)點(diǎn)
?????????*/
????????public?Node?left;
????????/**
?????????*?右節(jié)點(diǎn)
?????????*/
????????public?Node?right;

????????public?Node(int?value,?Node?left,?Node?right)?{
????????????this.value?=?value;
????????????this.left?=?left;
????????????this.right?=?right;
????????}
????}

????public?static?void?dfs(Node?treeNode)?{
????????if?(treeNode?==?null)?{
????????????return;
????????}
????????//?遍歷節(jié)點(diǎn)
????????process(treeNode)
????????//?遍歷左節(jié)點(diǎn)
????????dfs(treeNode.left);
????????//?遍歷右節(jié)點(diǎn)
????????dfs(treeNode.right);
????}
}

遞歸的表達(dá)性很好，也很容易理解，不過(guò)如果層級(jí)過(guò)深，很容易導(dǎo)致棧溢出。所以我們重點(diǎn)看下非遞歸實(shí)現(xiàn)

2、非遞歸實(shí)現(xiàn)

仔細(xì)觀察深度優(yōu)先遍歷的特點(diǎn)，對(duì)二叉樹來(lái)說(shuō)，由于是先序遍歷（先遍歷當(dāng)前節(jié)點(diǎn)，再遍歷左節(jié)點(diǎn)，再遍歷右節(jié)點(diǎn)），所以我們有如下思路

1. 對(duì)于每個(gè)節(jié)點(diǎn)來(lái)說(shuō)，先遍歷當(dāng)前節(jié)點(diǎn)，然后把右節(jié)點(diǎn)壓棧，再壓左節(jié)點(diǎn)（這樣彈棧的時(shí)候會(huì)先拿到左節(jié)點(diǎn)遍歷，符合深度優(yōu)先遍歷要求）
2. 彈棧，拿到棧頂?shù)墓?jié)點(diǎn)，如果節(jié)點(diǎn)不為空，重復(fù)步驟 1， 如果為空，結(jié)束遍歷。

我們以以下二叉樹為例來(lái)看下如何用棧來(lái)實(shí)現(xiàn) DFS。

整體動(dòng)圖如下

整體思路還是比較清晰的，使用棧來(lái)將要遍歷的節(jié)點(diǎn)壓棧，然后出棧后檢查此節(jié)點(diǎn)是否還有未遍歷的節(jié)點(diǎn)，有的話壓棧，沒(méi)有的話不斷回溯（出棧），有了思路，不難寫出如下用棧實(shí)現(xiàn)的二叉樹的深度優(yōu)先遍歷代碼:

/**
?*?使用棧來(lái)實(shí)現(xiàn)?dfs
?*?@param?root
?*/
public?static?void?dfsWithStack(Node?root)?{
????if?(root?==?null)?{
????????return;
????}

????Stack?stack?=?new?Stack<>();
????//?先把根節(jié)點(diǎn)壓棧
????stack.push(root);
????while?(!stack.isEmpty())?{
????????Node?treeNode?=?stack.pop();
????????//?遍歷節(jié)點(diǎn)
????????process(treeNode)

????????//?先壓右節(jié)點(diǎn)
????????if?(treeNode.right?!=?null)?{
????????????stack.push(treeNode.right);
????????}

????????//?再壓左節(jié)點(diǎn)
????????if?(treeNode.left?!=?null)?{
????????????stack.push(treeNode.left);
????????}
????}
}

可以看到用棧實(shí)現(xiàn)深度優(yōu)先遍歷其實(shí)代碼也不復(fù)雜，而且也不用擔(dān)心遞歸那樣層級(jí)過(guò)深導(dǎo)致的棧溢出問(wèn)題。

廣度優(yōu)先遍歷

廣度優(yōu)先遍歷，指的是從圖的一個(gè)未遍歷的節(jié)點(diǎn)出發(fā)，先遍歷這個(gè)節(jié)點(diǎn)的相鄰節(jié)點(diǎn)，再依次遍歷每個(gè)相鄰節(jié)點(diǎn)的相鄰節(jié)點(diǎn)。

上文所述樹的廣度優(yōu)先遍歷動(dòng)圖如下，每個(gè)節(jié)點(diǎn)的值即為它們的遍歷順序。所以廣度優(yōu)先遍歷也叫層序遍歷，先遍歷第一層（節(jié)點(diǎn) 1），再遍歷第二層（節(jié)點(diǎn) 2，3，4），第三層（5，6，7，8），第四層（9，10）。

深度優(yōu)先遍歷用的是棧，而廣度優(yōu)先遍歷要用隊(duì)列來(lái)實(shí)現(xiàn)，我們以下圖二叉樹為例來(lái)看看如何用隊(duì)列來(lái)實(shí)現(xiàn)廣度優(yōu)先遍歷

動(dòng)圖如下

相信看了以上動(dòng)圖，不難寫出如下代碼

/**
?*?使用隊(duì)列實(shí)現(xiàn)?bfs
?*?@param?root
?*/
private?static?void?bfs(Node?root)?{
????if?(root?==?null)?{
????????return;
????}
????Queue?stack?=?new?LinkedList<>();
????stack.add(root);

????while?(!stack.isEmpty())?{
????????Node?node?=?stack.poll();
????????System.out.println("value?=?"?+?node.value);
????????Node?left?=?node.left;
????????if?(left?!=?null)?{
????????????stack.add(left);
????????}
????????Node?right?=?node.right;
????????if?(right?!=?null)?{
????????????stack.add(right);
????????}
????}
}

習(xí)題演練

接下來(lái)我們來(lái)看看在 leetcode 中出現(xiàn)的一些使用 DFS，BFS 來(lái)解題的題目:

leetcode 104，111: 給定一個(gè)二叉樹，找出其最大/最小深度。

例如：給定二叉樹 [3,9,20,null,null,15,7],

????3
???/?\
??9??20
????/??\
???15???7

則它的最小深度 ?2，最大深度 3

解題思路：這題比較簡(jiǎn)單，只不過(guò)是深度優(yōu)先遍歷的一種變形，只要遞歸求出左右子樹的最大/最小深度即可，深度怎么求，每遞歸調(diào)用一次函數(shù)，深度加一。不難寫出如下代碼

/**
?*?leetcode?104:?求樹的最大深度
?*?@param?node
?*?@return
?*/
public?static?int?getMaxDepth(Node?node)?{
????if?(node?==?null)?{
????????return?0;
????}
????int?leftDepth?=?getMaxDepth(node.left)?+?1;
????int?rightDepth?=?getMaxDepth(node.right)?+?1;
????return?Math.max(leftDepth,?rightDepth);
}

/**
?*?leetcode?111:?求樹的最小深度
?*?@param?node
?*?@return
?*/
public?static?int?getMinDepth(Node?node)?{
????if?(node?==?null)?{
????????return?0;
????}
????int?leftDepth?=?getMinDepth(node.left)?+?1;
????int?rightDepth?=?getMinDepth(node.right)?+?1;
????return?Math.min(leftDepth,?rightDepth);
}

leetcode 102: 給你一個(gè)二叉樹，請(qǐng)你返回其按層序遍歷得到的節(jié)點(diǎn)值。（即逐層地，從左到右訪問(wèn)所有節(jié)點(diǎn)）。示例，給定二叉樹：[3,9,20,null,null,15,7]

????3
???/?\
??9??20
????/??\
???15???7

返回其層次遍歷結(jié)果：

[
??[3],
??[9,20],
??[15,7]
]

解題思路：顯然這道題是廣度優(yōu)先遍歷的變種，只需要在廣度優(yōu)先遍歷的過(guò)程中，把每一層的節(jié)點(diǎn)都添加到同一個(gè)數(shù)組中即可，問(wèn)題的關(guān)鍵在于遍歷同一層節(jié)點(diǎn)前，必須事先算出同一層的節(jié)點(diǎn)個(gè)數(shù)有多少（即隊(duì)列已有元素個(gè)數(shù)），因?yàn)?BFS 用的是隊(duì)列來(lái)實(shí)現(xiàn)的，遍歷過(guò)程中會(huì)不斷把左右子節(jié)點(diǎn)入隊(duì)，這一點(diǎn)切記！動(dòng)圖如下

根據(jù)以上動(dòng)圖思路不難得出代碼如下：

Java 代碼

/**
?*?leetcdoe?102:?二叉樹的層序遍歷,?使用?bfs
?*?@param?root
?*/
private?static?List>?bfsWithBinaryTreeLevelOrderTraversal(Node?root)?{
????if?(root?==?null)?{
????????//?根節(jié)點(diǎn)為空，說(shuō)明二叉樹不存在，直接返回空數(shù)組
????????return?Arrays.asList();
????}

????//?最終的層序遍歷結(jié)果
????List>?result?=?new?ArrayList<>();

????Queue?queue?=?new?LinkedList<>();
????queue.offer(root);

????while?(!queue.isEmpty())?{
????????//?記錄每一層
????????List?level?=?new?ArrayList<>();
????????int?levelNum?=?queue.size();
????????//?遍歷當(dāng)前層的節(jié)點(diǎn)
????????for?(int?i?=?0;?i?????????????Node?node?=?queue.poll();
????????????//?隊(duì)首節(jié)點(diǎn)的左右子節(jié)點(diǎn)入隊(duì),由于 levelNum 是在入隊(duì)前算的，所以入隊(duì)的左右節(jié)點(diǎn)并不會(huì)在當(dāng)前層被遍歷到
????????????if?(node.left?!=?null)?{
????????????????queue.add(node.left);
????????????}
????????????if?(node.right?!=?null)?{
????????????????queue.add(node.right);
????????????}
????????????level.add(node.value);
????????}
????????result.add(level);
????}

????return?result;
}

Python 代碼:

class?Solution:
????def?levelOrder(self,?root):
????????"""
????????:type?root:?TreeNode
????????:rtype:?List[List[int]]
????????"""
????????res?=?[]??#嵌套列表，保存最終結(jié)果
????????if?root?is?None:
????????????return?res
????????
????????from?collections?import?deque
????????que?=?deque([root])??#隊(duì)列，保存待處理的節(jié)點(diǎn)
????????while?len(que)!=0:
????????????lev?=?[]??#列表，保存該層的節(jié)點(diǎn)的值
????????????thislevel?=?len(que)??#該層節(jié)點(diǎn)個(gè)數(shù)
????????????while?thislevel!=0:
????????????????head?=?que.popleft()??#彈出隊(duì)首節(jié)點(diǎn)
????????????????#隊(duì)首節(jié)點(diǎn)的左右孩子入隊(duì)
????????????????if?head.left?is?not?None:
????????????????????que.append(head.left)
????????????????if?head.right?is?not?None:
????????????????????que.append(head.right)
????????????????lev.append(head.val)??#隊(duì)首節(jié)點(diǎn)的值壓入本層
????????????????thislevel-=1
????????????res.append(lev)
????????return?res

這題用 BFS 是顯而易見(jiàn)的，但其實(shí)也可以用 DFS， 如果在面試中能用 DFS 來(lái)處理，會(huì)是一個(gè)比較大的亮點(diǎn)。

用 DFS 怎么處理呢，我們知道， DFS 可以用遞歸來(lái)實(shí)現(xiàn)，其實(shí)只要在遞歸函數(shù)上加上一個(gè)「層」的變量即可，只要節(jié)點(diǎn)屬于這一層，則把這個(gè)節(jié)點(diǎn)放入相當(dāng)層的數(shù)組里，代碼如下：

private?static?final?List>?TRAVERSAL_LIST??=?new?ArrayList<>();
/**
?*?leetcdoe?102:?二叉樹的層序遍歷,?使用?dfs
?*?@param?root
?*?@return
?*/
private?static?void?dfs(Node?root,?int?level)?{
????if?(root?==?null)?{
????????return;
????}

????if?(TRAVERSAL_LIST.size()?1)?{
????????TRAVERSAL_LIST.add(new?ArrayList<>());
????}

????List?levelList?=?TRAVERSAL_LIST.get(level);
????levelList.add(root.value);

????//?遍歷左結(jié)點(diǎn)
????dfs(root.left,?level?+?1);

????//?遍歷右結(jié)點(diǎn)
????dfs(root.right,?level?+?1);
}

DFS，BFS 在搜索引擎中的應(yīng)用

我們幾乎每天都在 Google, Baidu 這些搜索引擎，那大家知道這些搜索引擎是怎么工作的嗎，簡(jiǎn)單來(lái)說(shuō)有三步

1、網(wǎng)頁(yè)抓取

搜索引擎通過(guò)爬蟲將網(wǎng)頁(yè)爬取，獲得頁(yè)面 HTML 代碼存入數(shù)據(jù)庫(kù)中

2、預(yù)處理

索引程序?qū)ψト?lái)的頁(yè)面數(shù)據(jù)進(jìn)行文字提取，中文分詞，（倒排）索引等處理，以備排名程序使用

3、排名

用戶輸入關(guān)鍵詞后，排名程序調(diào)用索引數(shù)據(jù)庫(kù)數(shù)據(jù)，計(jì)算相關(guān)性，然后按一定格式生成搜索結(jié)果頁(yè)面。

我們重點(diǎn)看下第一步，網(wǎng)頁(yè)抓取。

這一步的大致操作如下：給爬蟲分配一組起始的網(wǎng)頁(yè)，我們知道網(wǎng)頁(yè)里其實(shí)也包含了很多超鏈接，爬蟲爬取一個(gè)網(wǎng)頁(yè)后，解析提取出這個(gè)網(wǎng)頁(yè)里的所有超鏈接，再依次爬取出這些超鏈接，再提取網(wǎng)頁(yè)超鏈接。。。，如此不斷重復(fù)就能不斷根據(jù)超鏈接提取網(wǎng)頁(yè)。如下圖示

如上所示，最終構(gòu)成了一張圖，于是問(wèn)題就轉(zhuǎn)化為了如何遍歷這張圖，顯然可以用深度優(yōu)先或廣度優(yōu)先的方式來(lái)遍歷。

如果是廣度優(yōu)先遍歷，先依次爬取第一層的起始網(wǎng)頁(yè)，再依次爬取每個(gè)網(wǎng)頁(yè)里的超鏈接，如果是深度優(yōu)先遍歷，先爬取起始網(wǎng)頁(yè) 1，再爬取此網(wǎng)頁(yè)里的鏈接...，爬取完之后，再爬取起始網(wǎng)頁(yè) 2...

實(shí)際上爬蟲是深度優(yōu)先與廣度優(yōu)先兩種策略一起用的，比如在起始網(wǎng)頁(yè)里，有些網(wǎng)頁(yè)比較重要（權(quán)重較高），那就先對(duì)這個(gè)網(wǎng)頁(yè)做深度優(yōu)先遍歷，遍歷完之后再對(duì)其他（權(quán)重一樣的）起始網(wǎng)頁(yè)做廣度優(yōu)先遍歷。

總結(jié)

DFS 和 BFS 是非常重要的兩種算法，大家一定要掌握，本文為了方便講解，只對(duì)樹做了 DFS，BFS，大家可以試試如果用圖的話該怎么寫代碼，原理其實(shí)也是一樣，只不過(guò)圖和樹兩者的表示形式不同而已，DFS 一般是解決連通性問(wèn)題，而 BFS 一般是解決最短路徑問(wèn)題，之后有機(jī)會(huì)我們會(huì)一起來(lái)學(xué)習(xí)下并查集，Dijkstra, Prism 算法等，敬請(qǐng)期待！

覺(jué)得文章直擊靈魂，歡迎點(diǎn)贊、在看和轉(zhuǎn)發(fā)