本文內容基于《算法筆記》和官方配套練題網站“晴問算法”，是我作為小白的學習記錄，如有錯誤還請體諒，可以留下您的寶貴意見，不勝感激。

前言

深度優(yōu)先搜索是一種枚舉所有完整路徑以遍歷所有情況的搜索方法，總是以“深度”作為前進的關鍵詞。實現(xiàn)方式是有很多，最常見的是遞歸。

一、深度優(yōu)先搜索概述

深度優(yōu)先搜索屬于搜索問題的一種，當問題可以被描述為“路徑搜索”時，就可以采用搜素問題的所有解的方式來進行解決，所以DFS本質還是暴力。

深度搜索具有兩個關鍵詞，即“岔道口”和“死胡同”，這兩個詞來源于迷宮問題，這也是搜索問題最原始的表現(xiàn)。當碰到岔道口時，總是以“深度”作為前進的關鍵詞，不碰到死胡同就不回頭，因此被稱為“深搜”。深搜適合于求解需要遍歷所有解或路徑的問題，并且剪枝很重要。深搜和廣搜在數據結構中的應用就是對非線性存儲結構進行遍歷。

搜索和分治是兩大分析問題的方法，而回溯、剪枝、動態(tài)規(guī)劃可以說是對深度搜索和分治算法進行優(yōu)化。

二、算法設計

在使用遞歸進行DFS時，將遞歸式作為搜索中的“岔道口”，將遞歸邊界作為搜索中的“死胡同”，所以在設計DFS算法時，關鍵就是找準問題中的“岔道口”和“死胡同”。接下來通過實際例子介紹DFS，這里采用“晴問算法”中的題，書中的例題就不放了。

1.迷宮可行路徑數

這道題是接下來一系列問題的核心，下面的問題都是基于這道題進行局部修改。
首先分析“岔道口”：
每次移動可以選擇上下左右各一格進行移動，也就是說每次有四種選擇，即四個岔道口，設當前坐標為（x ，y），四個岔道口的選擇就分別為：（x+1，y），（x-1，y），（x，y+1），（x，y-1）。
其次分析“死胡同”：
當搜索到坐標位置元素為1時，表示無法通過，即無法繼續(xù)搜索，這時這條路徑便走到了盡頭；當搜索到終點時，就不用繼續(xù)搜索了。所以一共存在兩個遞歸邊界。
接下來就可以設計DFS（）函數：
根據上面“岔道口”的設計，我們需要設置初始狀態(tài)，即起點。用x表示行坐標，用y表示列坐標，所以函數看起來設這樣的：
void DFS(int x , int y , int n , int m){···}，當然，n和m可以放在外面。
遞歸邊界：
if(number[x][y] == 1) return; //死胡同
if(x == n && y == m) { //走到終點
countr++; //計數器
return;
}
岔路口的選擇：
需要路徑在可移動范圍內移動：不允許到曾經到過的地方并且不能出界，所以設置散列表標記曾經走過的位置，注意起點的狀態(tài)，不論哪條路起點肯定是必須走的。如果滿足移動條件，就沿岔路口移動。
完整代碼如下：

#include<cstdio>  //迷宮首先要確定起點和終點  
#include<algorithm>
#include<iostream> 
using namespace std;

const int MAXN = 5;
int number[MAXN][MAXN] = {};
int countr = 0;
bool hashTable[MAXN][MAXN] = {true}; //這就不是優(yōu)化了，如果不設這個條件，就會到達不了遞歸邊界 
//注意起點的狀態(tài)，肯定要經過起點 
void DFS(int x , int y , int n , int m){
	if(number[x][y] == 1)  return;  //死胡同 
	if(x == n && y == m) {
		countr++;
		return;
	}     //核心：四個岔路口 
	if(x + 1 <= n && hashTable[x + 1][y] == false) { //短路與，順序也不能亂，不然會報錯 
		hashTable[x + 1][y] = true;  //注意一定是先把狀態(tài)更新，先選上，再走 
		DFS(x + 1 , y , n , m);
		hashTable[x + 1][y] = false; //恢復狀態(tài) 
	}
	if(x - 1 >= 0 && hashTable[x - 1][y] == false) {
		hashTable[x - 1][y] = true;
		DFS(x - 1 , y , n , m);
		hashTable[x - 1][y] = false;
	}
	if(y + 1 <= m && hashTable[x][y + 1] == false) {
		hashTable[x][y + 1] = true;
		DFS(x , y + 1 , n , m);
		hashTable[x][y + 1] = false;
	} 
	if(y - 1 >= 0 && hashTable[x][y - 1] == false) {
		hashTable[x][y - 1] = true;
		DFS(x , y - 1 , n , m);
		hashTable[x][y - 1] = false;
	}
}

int main(){
	int n , m;
	scanf("%d%d", &n , &m);
	for(int i = 0; i <= n - 1; i++)
		for(int j = 0; j <= m - 1; j++)
			scanf("%d", &number[i][j]);
	DFS(0 , 0 , n - 1, m - 1);
	printf("%d", countr);
}

2.指定步數的迷宮問題

這個問題在第一個問題的基礎上更改計數器就可以了，相當于新加了一個遞歸深度的計數器。需要注意的是當存在滿足K步的路徑時，就不需要繼續(xù)搜索了，這時直接用回溯算法進行優(yōu)化，返回上一層。
完整代碼如下:

#include<cstdio>  //迷宮首先要確定起點和終點  
#include<algorithm>
#include<iostream> 
using namespace std;

const int MAXN = 5;
int number[MAXN][MAXN] = {};
bool flag = false;
int k;
bool hashTable[MAXN][MAXN] = {true}; //這就不是優(yōu)化了，如果不設這個條件，就會到達不了遞歸邊界 
//注意起點的狀態(tài)，肯定要經過起點 

void DFS(int x , int y , int n , int m , int countr){ //countr可以設成參數隨搜索動態(tài)變化，也可以像hashTable一樣恢復狀態(tài)，就是一個記錄遞歸深度的計數器 
	if(flag) return;
	if(number[x][y] == 1) {  //死胡同
		return;   
	}
	if(x == n && y == m) {
		if(countr == k) flag = true;
		return;
	}     //四個岔路口 
	if(x + 1 <= n && hashTable[x + 1][y] == false) { //短路與，順序也不能亂，不然會報錯 
		hashTable[x + 1][y] = true;  //注意一定是先把狀態(tài)更新，先選上，再走 
		DFS(x + 1 , y , n , m , countr+1);
		hashTable[x + 1][y] = false; //恢復狀態(tài) 
	}
	if(x - 1 >= 0 && hashTable[x - 1][y] == false) {
		hashTable[x - 1][y] = true;
		DFS(x - 1 , y , n , m , countr+1);
		hashTable[x - 1][y] = false;
	}
	if(y + 1 <= m && hashTable[x][y + 1] == false) {
		hashTable[x][y + 1] = true;
		DFS(x , y + 1 , n , m , countr+1);
		hashTable[x][y + 1] = false;
	} 
	if(y - 1 >= 0 && hashTable[x][y - 1] == false) {
		hashTable[x][y - 1] = true;
		DFS(x , y - 1 , n , m , countr+1);
		hashTable[x][y - 1] = false;
	}
}

int main(){
	int n , m;
	scanf("%d%d%d", &n , &m , &k);
	for(int i = 0; i <= n - 1; i++)
		for(int j = 0; j <= m - 1; j++)
			scanf("%d", &number[i][j]);
	DFS(0 , 0 , n - 1, m - 1 , 0);
	if(flag == true) printf("Yes");
	else printf("No");
}

3.矩陣最大權值

這道題也是加一個計數器就可以了，不過記錄的是權值，即坐標位置元素的值。
完整代碼如下：

#include<cstdio>  //迷宮首先要確定起點和終點  
#include<algorithm>
#include<iostream> //權值隨著搜索而動態(tài)改變 
using namespace std;

const int MAXN = 5;
int number[MAXN][MAXN] = {};
int MAX = -10e6;
bool hashTable[MAXN][MAXN] = {true}; //這就不是優(yōu)化了，如果不設這個條件，就會到達不了遞歸邊界 
//注意起點的狀態(tài)，肯定要經過起點 
void DFS(int x , int y , int n , int m , int value){
	if(x == n && y == m) {
		if(value > MAX) MAX = value;
		return;
	}     //核心：四個岔路口 
	if(x + 1 <= n && hashTable[x + 1][y] == false) { //短路與，順序也不能亂，不然會報錯 
		hashTable[x + 1][y] = true;  //注意一定是先把狀態(tài)更新，先選上，再走 
		DFS(x + 1 , y , n , m , value + number[x + 1][y]);
		hashTable[x + 1][y] = false; //恢復狀態(tài) 
	}
	if(x - 1 >= 0 && hashTable[x - 1][y] == false) {
		hashTable[x - 1][y] = true;
		DFS(x - 1 , y , n , m , value + number[x - 1][y]);
		hashTable[x - 1][y] = false;
	}
	if(y + 1 <= m && hashTable[x][y + 1] == false) {
		hashTable[x][y + 1] = true;
		DFS(x , y + 1 , n , m , value + number[x][y + 1]);
		hashTable[x][y + 1] = false;
	} 
	if(y - 1 >= 0 && hashTable[x][y - 1] == false) {
		hashTable[x][y - 1] = true;
		DFS(x , y - 1 , n , m , value + number[x][y - 1]);
		hashTable[x][y - 1] = false;
	}
}

int main(){
	int n , m;
	scanf("%d%d", &n , &m);
	for(int i = 0; i <= n - 1; i++)
		for(int j = 0; j <= m - 1; j++)
			scanf("%d", &number[i][j]);
	DFS(0 , 0 , n - 1, m - 1 , number[0][0]);
	printf("%d", MAX);
}

4.矩陣最大權值路徑

這道題可以開數組記錄走過的坐標，并設置最大權值之和路徑數組，如果權值之和更大，交換數組。注意更新數組狀態(tài)，不要影響其他路徑的選擇。
完整代碼如下：

#include<cstdio>  //迷宮首先要確定起點和終點  
#include<algorithm>
#include<iostream> //權值隨著搜索而動態(tài)改變 
#include<vector>//這里也不知道開多長，就用vector實現(xiàn)吧 , 這道題是前面的整合,走一步記一下，如果權值更大，更新結果數組 
using namespace std;
const int MAXN = 5;
int number[MAXN][MAXN] = {};
int MAX = -10e6;
vector <int> temp , ans;
bool hashTable[MAXN][MAXN] = {true}; //這就不是優(yōu)化了，如果不設這個條件，就會到達不了遞歸邊界  
//注意起點的狀態(tài)，肯定要經過起點 
void DFS(int x , int y , int n , int m , int value){
	if(x == n && y == m) {
		if(value > MAX) {
			MAX = value;
			ans = temp;
		}
		return;
	}     //核心：四個岔路口 
	if(x + 1 <= n && hashTable[x + 1][y] == false) { //短路與，順序也不能亂，不然會報錯 
		hashTable[x + 1][y] = true;  //注意一定是先把狀態(tài)更新，先選上，再走 
		temp.push_back(x + 1); 
		temp.push_back(y); 
		DFS(x + 1 , y , n , m , value + number[x + 1][y]);
		hashTable[x + 1][y] = false; //恢復狀態(tài) 
		temp.pop_back();
		temp.pop_back();
	}
	if(x - 1 >= 0 && hashTable[x - 1][y] == false) {
		hashTable[x - 1][y] = true;
		temp.push_back(x - 1) ; 
		temp.push_back(y);
		DFS(x - 1 , y , n , m , value + number[x - 1][y]);
		hashTable[x - 1][y] = false;
		temp.pop_back();
		temp.pop_back();
	}
	if(y + 1 <= m && hashTable[x][y + 1] == false) {
		hashTable[x][y + 1] = true;
		temp.push_back(x) ; 
		temp.push_back(y + 1);
		DFS(x , y + 1 , n , m , value + number[x][y + 1]);
		hashTable[x][y + 1] = false;
		temp.pop_back();
		temp.pop_back();
	} 
	if(y - 1 >= 0 && hashTable[x][y - 1] == false) {
		hashTable[x][y - 1] = true;
		temp.push_back(x) ; 
		temp.push_back(y - 1);
		DFS(x , y - 1 , n , m , value + number[x][y - 1]);
		hashTable[x][y - 1] = false;
		temp.pop_back();
		temp.pop_back();
	}
}

int main(){
	int n , m;
	scanf("%d%d", &n , &m);
	for(int i = 0; i <= n - 1; i++)
		for(int j = 0; j <= m - 1; j++)
			scanf("%d", &number[i][j]);
	temp.push_back(0);temp.push_back(0);  
	DFS(0 , 0 , n - 1, m - 1 , number[0][0]);
	for(vector<int> :: iterator it = ans.begin(); it != ans.end(); it = it + 2){  //迭代器遍歷
		printf("%d %d\n", *it + 1 , *(it + 1) + 1);
	}
		
}

三、備注

1.遞歸只是一種實現(xiàn)方法，分治法和搜索都可以采用遞歸實現(xiàn)，且相對其他方法更簡單，只是運行效率低且容易爆站，所以需要算法優(yōu)化；
2.分治法和搜索雖然實現(xiàn)方式都是遞歸，但在分析問題時是兩種不同的是思想；
3.回溯優(yōu)化是指當遞歸滿足某些條件時就可以停止遞歸返回上一層，所以回溯的前提是必須存在可行解保證可以走到遞歸邊界，否則會死遞歸；
4.剪枝優(yōu)化是指在面對岔路口時，在滿足某些條件時，可以減少岔路口的選擇；
5.注意優(yōu)化和遞歸邊界的區(qū)別，遞歸邊界是問題必須滿足的最后條件，而優(yōu)化是在題目條件的限制上來減少計算量；
6.搜索算法并不只存在于數據結構的圖論中，雖然最初接觸DFS和BFS時是在數據結構中，但實際這是一種算法，當問題滿足可以搜索的性質時，就可以運用搜索算法；
7.注意遞歸中參數的作用域；
8.全排列適合用分治解決，組合適合用搜索解決；文章來源地址http://www.zghlxwxcb.cn/news/detail-718338.html

到了這里，關于深度優(yōu)先搜索（DFS）（算法筆記）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！