深度優先搜尋 —— 新手上路的一道坎

作者：由英雄哪裡出來發表于舞蹈時間：2021-12-04

前言

深度優先搜尋

的實現是

遞迴

，一直是新手程式設計師上路的一道坎。記得剛開始學遞迴的時候，無論怎麼看這個程式碼都覺得不對勁，一直都理解不了，後來透過不斷刷題，不斷總結，終於有了眉目。有些時候，當你理解不了的時候，最好把圖畫出來，可能會清晰很多，那麼這篇文章，作者就來用動圖的形式講解

深度優先搜尋

的整個過程。

一、搜尋演算法的原理

搜尋演算法的原理就是列舉。利用計算機的高效能，給出人類制定好的規則，枚舉出所有可行的情況，找到可行解或者最優解。

比較常見的搜尋演算法是深度優先搜尋（又叫深度優先遍歷）和廣度優先搜尋（又叫廣度優先遍歷或者寬度優先遍歷）。各種圖論的演算法基本都是依靠這兩者進行展開的。

深度優先搜尋一般用來求可行解，利用剪枝進行最佳化，在樹形結構的圖上用處較多；而廣度優先搜尋一般用來求最優解，配合雜湊表進行狀態空間的標記，從而避免重複狀態的計算；

二、深度優先搜尋

1、DFS

1）演算法原理

深度優先搜尋（Depth First Search），是圖遍歷演算法的一種。用一句話概括就是：“一直往下走，走不通回頭，換條路再走，直到無路可走”。具體演算法描述為：

選擇一個起始點

作為

當前結點

，執行如下操作：

a。訪問當前結點，並且標記該結點已被訪問，然後跳轉到 b；

b。如果存在一個和當前結點相鄰並且尚未被訪問的結點

，則將

設為當前結點，繼續執行 a；

c。如果不存在這樣的

，則進行回溯，回溯的過程就是回退當前結點；

上述所說的

當前結點

需要用一個棧來維護，每次訪問到的結點入棧，回溯的時候出棧。除了棧，另一種實現深度優先搜尋的方式是遞迴，程式碼更加簡單，相對好理解。

【例題1】給定一個 n 個結點的無向圖，要求從 0 號結點出發遍歷整個圖，求輸出整個過程的遍歷序列。其中，遍歷規則為：

1）如果和當前結點相鄰的結點已經訪問過，則不能再訪問；

2）每次從和當前結點相鄰的結點中尋找一個編號最小的沒有訪問的結點進行訪問；

如圖1所示，對上圖以深度優先的方式進行遍歷，起點是 0；

<1> 第一步，當前結點為 0，標記已訪問，然後從相鄰結點中找到編號最小的且沒有訪問的結點 1；

<2> 第二步，當前結點為 1，標記已訪問，然後從相鄰結點中找到編號最小的且沒有訪問的結點 3；

<3> 第三步，當前結點為 3，標記已訪問，沒有尚未訪問的相鄰結點，執行回溯，回到結點 1；

<4> 第四步，當前結點為 1，從相鄰結點中找到編號最小的且沒有訪問的結點 4；

<5> 第五步，當前結點為 4，標記已訪問，然後從相鄰結點中找到編號最小的且沒有訪問的結點 5；

<6> 第六步，當前結點為 5，標記已訪問，然後從相鄰結點中找到編號最小的且沒有訪問的結點 2；

<7> 第七步，當前結點為 2，標記已訪問，然後從相鄰結點中找到編號最小的且沒有訪問的結點 6；

<8> 第八步，當前結點為 6，標記已訪問，沒有尚未訪問的相鄰結點，執行回溯，回到結點 2；

<9> 第九步，按照 2 => 5 => 4 => 1 => 0 的順序一路回溯，搜尋結束；

如下圖所示，紅色實箭頭表示搜尋路徑，藍色虛箭頭表示回溯路徑。

圖中，紅色塊表示往下搜尋，藍色塊表示往上回溯，遍歷序列為：

2）演算法實現

const

int

MAXN

；

void

dfs

（

int

）

{

（

visit

［

］）

{

// 1

return

；

}

visit

［

］

true

；

// 2

dfs_add

（

）；

// 3

for

（

int

；

MAXN

；

）

{

int

；

（

adj

［

］［

］）

{

// 4

dfs

（

）；

// 5

}

1、

visit［MAXN］

陣列是一個bool陣列，用於標記某個節點是否已訪問，初始化都為 false；這裡對已訪問結點執行回溯；

2、

visit［u］ = true；

對未訪問結點

標記為已訪問狀態；

3、

dfs_add（u）；

用來將

儲存到的訪問序列中，實際函式實現如下：

void

dfs_add

（

int

）

{

ans

［

ansSize

］

；

}

4、

adj［MAXN］［MAXN］

是圖的鄰接矩陣，用 0 或 1 來代表點是否連通，對於上面的例子，鄰接矩陣表示如下：

bool

adj

［

MAXN

］［

MAXN

］

{

，

}，

{

，

}，

{

，

}，

{

，

}，

{

，

}，

{

，

}，

{

，

}，

}；

（

adj［u］［v］ = 1

代表 u 和 v 之間有一條有向邊；

adj［u］［v］ = 0

代表沒有邊）

5、遞迴呼叫相鄰結點；

3）基礎應用

a. 求階乘

【例題2】給出

$n ( n \le 10 )$

，求

；

令

，那麼有

。由於滿足遞迴的性質，可以認為這是一個

個結點的圖，結點

$i (i \ge 1)$

到結點

有一條權值為

的有向邊，從

開始進行深度優先搜尋，搜尋的終點是結點

，返回值為

（即

）。

如圖所示，

的遞迴計算看成是一個

深度優先搜尋

的過程，紅色路徑代表遞迴往下搜尋，藍色路徑代表回溯，並且每次回溯的時候會將遍歷的結果返回給上一個結點（當然，這只是一個思想，並不代表這是求

的高效演算法）。

C++ 程式碼實現如下：

int

dfs

（

int

）

{

return

！

？

：

dfs

（

）；

}

由於 C++ 中的 int 是 32 位整數，最大能夠表示的值為

$2^{31}-1$

，所以這裡的 n 太大就會導致溢位，需要用陣列來模擬實現高精度。

b. 求斐波那契數列的第n項

【例題3】令

，

，其中

；

同樣可以利用圖論的思想，從結點

向

和

分別引一條權值為

的有向邊，每次求

就是以

作為起點，對

進行深度優先搜尋，然後將

和

回溯的結果相加作為

結點的值，即

。

C++ 程式碼實現如下：

int

dfs

（

unsigned

int

）

{

（

）

{

return

；

}

return

dfs

（

）

dfs

（

）；

}

例如，

的計算流程如圖所示：

這裡會帶來一個問題，

的計算需要用到

和

，而

的計算需要用到

和

，所以我們發現

被用到了兩次，而且每個結點都存在這個問題，這樣就使得整個演算法的時間複雜度變成指數級了，對於斐波那契數列遞迴演算法的時間複雜度分析，可以參考這篇文章：斐波那契數列遞迴時間複雜度分析

為了規避這個問題，下面會講到基於深搜的記憶化搜尋。

c. 求 n 個數的全排列

【例題4】給定

，按字典序輸出 1 到

的所有全排列；

全排列的種數是

，要求按照字典序輸出。這是最典型的深搜問題。我們可以把

個數兩兩建立無向邊（即任意兩個結點之間都有邊，也就是一個

個結點的完全圖），然後對每個點作為起點，分別做一次深度優先搜尋，當所有點都已經標記時，輸出當前的搜尋路徑，就是其中一個排列；

這裡需要注意的是，回溯的時候需要將原先標記的點的標記取消，否則只能輸出一個排列。如果要按照字典序，則需要在遍歷的時候保證每次遍歷都是按照結點從小到大的方式進行遍歷的。

如下圖所示，代表了一個 3個數的全排列的深度優先搜尋空間樹；

C++ 程式碼實現如下：

void

dfs

（

int

depth

）

{

// 1

（

depth

MAXN

）

{

// 2

dfs_print

（）；

return

；

}

for

（

int

；

MAXN

；

）

{

int

；

（

！

visit

［

］）

{

// 3

dfs_add

（

）；

// 4

dfs

（

depth

）；

dfs_dec

（

）；

}

1）這裡的

depth

引數用來做計數用，表明本次遍歷了多少個結點；

2）當遍歷元素達到

MAXN

個的時候，輸出訪問的元素列表；

3）

visit［v］

用來判斷

這個元素是否有訪問過；

4）

dfs_add

和

dfs_dec

分別表示將結點從訪問列表加入和刪除；

void

dfs_add

（

int

）

{

visit

［

］

true

；

ans

［

ansSize

］

；

ansSize

；

}

void

dfs_dec

（

int

）

{

——

ansSize

；

visit

［

］

false

；

}

4）高階應用

a. 列舉

資料範圍較小的的排列、組合的窮舉。

b. 容斥原理

主要用於組合數學中的計數統計，會在後面的章節詳細介紹。

c. 基於狀態壓縮的動態規劃

一般解決棋盤擺放問題，k 進製表示狀態，然後利用深搜進行狀態轉移，會在後面的章節詳細介紹。

d.記憶化搜尋

某個狀態已經被計算出來，就將它 cache 住，利用陣列或者雜湊表將它的值儲存下來，下次要用的時候不需要重新求，此所謂記憶化。

e.有向圖強連通分量

經典的 Tarjan 演算法，求解 2-sat 問題的基礎，會在後面的章節詳細介紹。

f. 無向圖割邊割點和雙連通分量

經典的 Tarjan 演算法，會在後面的章節詳細介紹。

g. LCA 最近公共祖先

最近公共祖先遞迴求解，會在後面的章節詳細介紹。

h.博弈

利用深搜計算SG值，會在後面的章節詳細介紹。

i.二分圖最大匹配

經典的匈牙利演算法，最小頂點覆蓋、最大獨立集、最小值支配集向二分圖的轉化，會在後面的章節詳細介紹。

j.歐拉回路

經典的圈套圈演算法，會在後面的章節詳細介紹。

k.K短路

依賴資料，資料不卡的話可以採用2分答案 + 深搜；也可以用廣搜 + A。

l. 線段樹

二分經典思想，配合深搜列舉左右子樹，求和、最值等問題，會在後面的章節詳細介紹。

m. 最大團

極大完全子圖的最佳化演算法，會在後面的章節詳細介紹。

n. 最大流

EK演算法求任意路徑中有涉及，會在後面的章節詳細介紹。

o. 樹形DP

即樹形動態規劃，父結點的值由各個子結點計算得出，會在後面的章節詳細介紹。

2、基於DFS的記憶化搜尋

1）演算法原理

上文中已經提到記憶化搜尋，其實就是類似動態規劃的思想，每次將已經計算出來的狀態的值儲存到陣列或者雜湊表中，下次需要的時候直接記錄的值，避免重複計算。

【例題5】如圖所示，圖中的橙色小方塊就是傳說中的作者，他可以在一個

的棋盤上行走，但是隻有兩個方向，一個是向右，一個是向下（如綠色箭頭所示），棋盤上有很多的金礦，走到格子上就能取走那裡的金礦，每個格子的金礦數目不同（用藍色數字表示金礦的數量），問作者在這樣一個棋盤上最多可以拿到多少金礦。

我們用函式

表示從

到

可以取得金礦的最大值，那麼要到達

這個點，要麼是從

過來，要麼是從

過來，所以就有如下遞迴式：

$d(i, j) = gold[i][j] + \max \{ d(i, j-1), d(i-1, j) \}\\$

滿足遞迴性質就可以進行深度優先搜尋了，於是遇到了和求斐波那契數列一樣的問題，

可能會被計算兩次，每個結點都被計算兩次的話複雜度就是指數級了（即至少

）。

所以這裡我們可以利用一個二維陣列，令

，初始化所有的

，表示尚未計算，每次搜尋到

這個點時，檢查

的值，如果為

，則進行計算，將計算結果賦值給

；否則直接返回

的值。

記憶化搜尋雖然叫搜尋，實際上還是一個動態規劃問題，能夠記憶化搜尋的一般都能用動態規劃求解，但是記憶化搜尋的編碼更加直觀、易寫。

2）演算法實現

C++ 程式碼實現如下：

int

dfs

（

int

，

int

）

{

（

）

{

// 1

return

［

］［

］

gold

［

］［

］；

}

（

）

{

// 2

return

；

}

（

［

］［

］

！=

）

{

// 3

return

［

］［

］；

}

return

［

］［

］

gold

［

］［

］

max

（

dfs

（

，

），

dfs

（

，

））；

// 4

}

1）當 i 和 j 都為 0，代表起點，直接返回起點的金礦值；

2）當 i < 0 或者 j < 0 時，代表是個不合法的點，則直接返回最小值 0；

3）當

不等於預設值

時，說明之前已經透過其他途徑遍歷到

這個點並且已經計算過最優值，可以直接返回。

4）利用遞迴計算

這個點的最優值，並且賦值給

作為記憶化。

樣例的計算結果如下：

關於記憶化搜尋的內容，本文只作簡要入門級介紹，更加詳細的內容，可以參考這篇文章：

3、基於DFS的剪枝

1）演算法原理

搜尋的過程可以看作是從樹根出發，遍歷一棵倒置的樹——搜尋樹的過程。而剪枝，顧名思義，就是透過某種判斷，避免一些不必要的遍歷過程，形象的說，就是剪去了搜尋樹中的某些“枝條”，故稱剪枝（原話取自1999年OI國家集訓隊論文《搜尋方法中的剪枝最佳化》（齊鑫））。

如圖三-8所示，它是一棵利用深度優先搜尋遍歷的搜尋樹，可行解（或最優解）位於綠色的葉子結點，那麼根結點的最左邊的子樹完全沒有必要搜尋（因為不可能出解）。如果我們在搜尋的過程中能夠清楚地知道哪些子樹不可能出解，就沒必要往下搜尋了，也就是將連線不可能出解的子樹的那根“枝條”剪掉，圖中紅色的叉對應的“枝條”都是可以剪掉的。

好的剪枝可以大大提升程式的執行效率，那麼問題來了，如何進行剪枝？我們先來看剪枝需要滿足什麼原則：

a. 正確性

剪掉的子樹中如果存在可行解（或最優解），那麼在其它的子樹中很可能搜不到解導致搜尋失敗，所以剪枝的前提必須是要正確；

b. 準確性

剪枝要“準”。所謂“準”，就是要在保證在正確的前提下，儘可能多得剪枝。

c. 高效性

剪枝一般是透過一個函式來判斷當前搜尋空間是否是一個合法空間，在每個結點都會呼叫到這個函式，所以這個函式的實現效率很重要。剪枝大致可以分成兩類：可行性剪枝、最優性剪枝（上下界剪枝）。

2）可行性剪枝

可行性剪枝一般是處理可行解的問題，如一個迷宮，問能否從起點到達目標點之類的。

【例題6】如圖所示，問作者能否在正好第 11 秒的時候避過各種障礙物（圖中的東西一看就知道哪些是障礙物了，^_^）最終取得愛心，作者每秒能且只能移動一格，允許走重複的格子。

仔細分析可以發現，這是永遠不可能的，因為作者無論怎麼走，都只能在第偶數秒的時候到達愛心的位置，這是他們的曼哈頓距離（兩點的XY座標差的絕對值之和）的奇偶性決定的，所以這裡我們可以在搜尋的時候做奇偶性剪枝（可行性剪枝）。

類似的求可行解的問題還有很多，如

$N (N \le 25)$

根長度不一的木棒，問能否選取其中幾根，拼出長度為

的木棒，具體就是列舉取木棒的過程，每根木棒都有取或不取兩種狀態，所以總的狀態數為

$2^{25}$

，需要進行剪枝。用到的是剩餘和不可達剪枝（隨便取的名字，即當前

根木棒取了

根後，剩下的

根木棒的總和加上之前取的

根木棒總和如果小於

，那麼必然不滿足，沒必要繼續往下搜尋了），這個問題其實是個 01揹包，當 N 比較大的時候就是動態規劃了。有關 0/1 揹包的內容，可以參考這篇文章：

3）最優性剪枝（上下界剪枝）

最優性剪枝一般是處理最優解的問題。以求兩個狀態之間的最小步數為例，搜尋最小步數的過程：一般情況下，需要儲存一個“當前最小步數”，這個最小步數就是當前解的一個下界d。在遍歷到搜尋樹的葉子結點時，得到了一個新解，與儲存的下界作比較，如果新解的步數更小，則令它成為新的下界。搜尋結束後，所儲存的解就是最小步數。而當我們已經搜尋了k歩，如果能夠透過某種方式估算出當前狀態到目標狀態的理論最少步數 s 時，就可以計算出起點到目標點的理論最小步數，即估價函式 h = k + s，那麼當前情況下存在最優解的必要條件是h < d，否則就可以剪枝了。最優性剪枝是不斷最佳化解空間的過程。

關於剪枝技巧還有很多，本文就不多展開了，後面章節會專門對剪枝技巧進行一個梳理，詳細剖析每個問題。

4、基於DFS的A*（迭代加深，IDA*）

1）演算法原理

迭代加深就是深度優先搜尋加上 A* 估價函式進行剪枝，應用相對較為侷限，但是對於處理某些問題有奇效，本文會舉一個比較簡單的例子，後面章節會詳細展開來講以加深理解。

迭代加深演算法原理如下：

1、列舉深度。

2、根據限定的深度進行 dfs，並且利用估價函式進行剪枝。

演算法原理本身很簡單，難點在於估價函式的選取和實現。

2）演算法實現

void

IDA_Star

（

int

startState

）

{

int

maxDepth

；

while

（

true

）

{

（

dfs

（

startState

，

maxDepth

））

{

return

；

}

maxDepth

；

}

3）簡單舉例

【例題7】如圖所示，一個“井”字形的玩具，上面有三種數字1、2、3，給出8種操作方式，A表示將第一個豎著的列迴圈上移一格，並且A和F是一個逆操作，B、C、D。。。的操作方式依此類推，初始狀態給定，目標狀態是中間8個數字相同。問最少的操作方式，並且要求給出操作的序列，步數一樣的時候選擇字典序最小的輸出。圖中的操作序列為AC。