DFS介紹：
DFS 全稱是 Depth First Search ，中文名是深度優先搜索，是一種用于遍歷或搜索樹或圖的演算法，
該演算法講解時常常與 BFS 并列，但兩者除了都能遍歷圖的連通塊以外，用途完全不同，很少有能混用兩種演算法的情況，
DFS 最顯著的特征在于其遞回呼叫自身 ，同時與 BFS 類似，DFS 會對其訪問過的點打上訪問標記，在遍歷圖時跳過已打過標記的點，以確保 每個點僅訪問一次 ，符合以上兩條規則的函式，便是廣義上的 DFS，
DFS的思路：所謂深度優先，就是說每次都嘗試向更深的節點走，
DFS優化：DFS是暴搜，改寫成記憶化搜索之類的，或者剪枝（break一些分支）都可以優化（待補充），
DFS的板子大致如下：
void dfs(int step)
{
if(走到邊界)
{
操作();//輸出答案等
return;
}
else
{
for()//列舉方向等
if(滿足進一步搜索條件)
{
標記為訪問;
search(step+1);
識訓標記;//回溯
}
}
}
這個板子看上去比較易懂，但其細節還是值得思考的，下面以幾個經典題目為例子，決議DFS相關陳述句，
例題1：求1-n全排列
這是DFS求全排列的板子，喜歡的可以點擊拿走（
題目大意：就是求1-n全排列
首先，我們可以模擬一下求全排列這個程序（參考了《啊哈！演算法》）
這里模擬n=3的情況
我們有三張卡牌1,2,3 并且有三個卡槽，現在要將三張牌放入三個卡槽中，從第一個卡槽開始出發，首先我們向第一個卡槽放入1，然后繼續向前走，依次放入2,3，并向前走（到第三個卡槽后一步），此時，得到了第一個序列1,2,3，（靈魂配圖預警）
而且，我們的手中已經沒有卡牌了，所以要回退，在回到第三個卡槽的時候，識訓第三張牌（這里是3），然而此時若放下3便和剛才的情況重復，于是繼續回退識訓第二張牌（這里是2），在完成識訓第二張牌的動作之后，我們手上有了2,3，于是便可以將3放入第二個卡槽，向前走，將2放入地三個卡槽，得到第二個序列1,3,2，
類似地，可以得到1-3的全排列，
模擬完后我們就可以輕松寫出代碼了
現在上代碼：（先看看注釋理解一下吧）
#include<iostream>
using namespace std;
int a[100001],n;
bool book[100001];//判斷是否被訪問
void dfs(int step){
// if(滿足所需要的條件) { 相應的操作；return；}
if(step==n+1){
for(int i=1;i<=n;i++) printf("%d ",a[i]);//列印
cout<<endl;
return;
}
//列舉
for(int i=1;i<=n;i++)
{
if(book[i]==0)
{
a[step]=i;//記錄資料
book[i]=1;//記錄相應的數已經被訪問
dfs(step+1);//進一步搜索
book[i]=0;//恢復到未被訪問
}
}
}
int main(){
cin>>n;
dfs(1);//從一開始搜索并且列印
return 0;
}
很多陳述句都是很好理解的，但是不是還是一頭霧水
那么只要解決幾個難懂的問題就可以了
現在需要決議的是：
Q1：這個函式實作了什么？
先撇開判定搜完一輪的if陳述句，這個函式其實就是for回圈套著for回圈，他的本質其實與n個for回圈無異，但是為什么要這樣子寫？就是因為n可能很大，用for一直寫可能實作不了，所以這個函式的功能就是暴力依次列舉1-n的全排列（可以試試n=3只用for回圈實作就可以理解了），
Q2：如下，這里的return陳述句到底回傳到了哪里？
// if(滿足所需要的條件) { 相應的操作；return；}
if(step==n+1){
for(int i=1;i<=n;i++) printf("%d ",a[i]);//列印
cout<<endl;
return;
}這個問題困擾了我很久，在被dalao教做人與dalao討論后，我得到了較為清楚的解釋，
return的作用無非是回傳，結束該層的函式，而在這個函式中，便是結束了一個dfs(n+1),回到了dfs(n)中（第n層回圈），并繼續執行dfs(n)中的陳述句，比如這里是回到第二個陳述句中：
1 dfs(step+1);
2 book[i]=0;//恢復到未被訪問 拿剛才的模擬程序來說：就是我們已經走到第三個卡槽之后，開始回退，
Q3：為什么回退之后拿回第一張牌（比如模擬中的第三個卡槽的牌）之后，不會出現立即將該牌放入相應卡槽出現死回圈的現象呢？
以模擬程序為例，回到程式中，不難發現，此時的回圈中的i=4，已經跳出這層回圈了，自然地，回到了上一層回圈（也就是第二個卡槽中，實作了回退），
（待補充）
解決了這些問題之后，大概就能夠比較清楚地了解DFS的作業原理了，
下面用遞回樹來刻畫DFS實作的程序以加深理解（以求1-3的全排列為例）：
前方靈魂圖示預警
從第一個結點出發，開始搜索~
根據DFS的思路，搜到無路可走開始回退，
類似地，繼續往下搜，直到得到所有答案：
例2：迷宮
題目大意：就是給你一個迷宮（廢話），迷宮有一些障礙，需要你求從起點坐標到終點坐標的方案總數，
題目鏈接
下面貼出代碼以供參考：
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
int map[10][10];//存圖
int x,y;//記錄起點坐標
int px,py;//記錄終點坐標
int m,n,t;
int a,b;//記錄障礙點
ll ans=0;//初始化ans
const int dx[4]={0,0,-1,1};//x direction
const int dy[4]={1,-1,0,0};//y direction
void dfs(int x,int y){
if(x==px&&y==py)//到達終點
{
ans++;
return;
}
else{
for(int i=0;i<4;i++)
{
int kx=x+dx[i];int ky=y+dy[i];//進行移動
//判定是否越界 有障礙 已經訪問過
if(kx<1||ky<1||kx>m||ky>n||map[kx][ky]==1||map[kx][ky]==2)continue;
map[kx][ky]=1;//標記已經訪問
dfs(kx,ky);
map[kx][ky]=0;
}
}
}
int main(){
cin>>n>>m>>t;
cin>>x>>y;cin>>px>>py;
while(t--){
cin>>a>>b;
map[a][b]=2;
}
map[x][y]=1;//初始化，標記起點為已經訪問
dfs(x,y);//從起點開始搜
cout<<ans;
return 0;
}DFS易錯點
初學DFS，很容易會寫出bug，這里就放一些出現錯誤的代碼供讀者閱讀、修改，同時我也會貼出正確代碼并加以決議，
例1：租用游艇（題目請點擊下面的鏈接~）
https://www.luogu.com.cn/problem/P1359
決議：這道題本來不是DFS解的題，但是用DFS+剪枝也能夠過，所以就貼出來了~
思路：這題其實就是求最短路，不懂的可以畫一下圖，我們只需要暴搜將所有的路徑長度求出并不斷更新答案就可以了，
圖示:
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
using namespace std;
typedef unsigned long long ll;
int map[201][201]; //map[i][j]:結點i->j的鍵值
int ans=1e7;//初始化ans為足夠大
int n;
void dfs(int step,int temp){
if(temp>ans) return;//剪枝
if(step==n){
ans=min(ans,temp);//更新答案
return;
}
for(int i=step+1;i<=n;i++){
step=i;
dfs(step,temp+map[step][i]);
}
}
int main(){
cin>>n;
for(int i=1;i<=n-1;i++)
{
for(int j=i+1;j<=n;j++)
{
scanf("%d",&map[i][j]);
}
}//讀入
dfs(1,0);
cout<<ans<<endl;
return 0;
}請讀者先看看上面的代碼有什么問題，
問題出在這里：
for(int i=step+1;i<=n;i++){
step=i;
dfs(step,temp+map[step][i]);
}如果將step賦值為i，那么回圈的時候會出現問題，
而改成這樣：
for(int i=step+1;i<=n;i++){
dfs(i,temp+map[step][i]);
}便可以保證回圈的正常進行，因為在這層for中，i可以逐個列舉接下來要到的結點，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/121419.html
標籤：其他