DFS算法：

上周學習了貪心算法和dp算法，因為經常在leetcode的題解看到dfs算法，在藍橋杯也有很多dfs相關題目，這周開始學習dfs算法。

---

思路講解：

dfs算法就是深度優先搜索，它優先考慮搜索的深度，當搜索到結束條件，也就是結束條件之后就退回一步重新搜索，光看思路太過抽象了，我們可以通過例題來認識dfs算法。

---

例題：

1.全排列問題：

全排列在學習高中數學排列組合的時候經常會用到，而要實現全排列也很適合用dfs的方法來解決，我們設置將n個不同數字的小球放到不同數字的箱子里。

---

思路：

• 首先，我們設置dfs的條件，就是當放到最后一個箱子的時候，開始退回一步
• 接著，我們寫出主要代碼，那就是從最小的小球開始，往右開始放小球
• 最后，寫上類似于dfs(n+1)的代碼，讓小球在取出之后，繼續往下進行搜索

---

代碼：

#include<stdio.h> int a[10],b[10],n; void put(int box) { int i;if(box == n+1)//put函數的結束標志，返回上一級函數 { for(i = 1; i <= n; i++){printf("%d",a[i]);}printf("\n");return ;//返回上一級的put函數 }for(i = 1; i <= n; i++){if(b[i] == 0){ a[box] = i;b[i] = 1;put(box+1); b[i] = 0;}}return ;//返回上一級的put函數 } int main(){scanf("%d",&n);put(1); return 0; }

---

運行結果：

運行結果

---

2.全排列問題拓展:

題干：

在1到9這9個數中排列出一個三位數相加的等式

---

思路：

這道題可以通過暴力遍歷來解決，但暴力遍歷的方法需要用到9重循環，這意味著很高的時間復雜度，所以可以利用dfs算法進行深搜

---

代碼：

#include<stdio.h> int n[10],record[10],sum; void add(int box) { int i;if(box == 10){ if(n[1]*100+n[2]*10+n[3]+n[4]*100+n[5]*10+n[6]==n[7]*100+n[8]*10+n[9]){sum++;printf("%d%d%d+%d%d%d = %d%d%d\n",n[1],n[2],n[3],n[4],n[5],n[6],n[7],n[8],n[9]);} return ; //返回上一級函數 } for(i = 1; i <= 9; i++){if(record[i]==0){ n[box]=i;record[i]=1;add(box+1);record[i]=0;}}return;//返回上一級函數 } int main() {add(1); //函數從1開始 printf("%d",sum/2);return 0; }

---

運行結果：

---

迷宮問題（最短路徑）：

題干：

這題的題干大意就是，求（1，1）位置到（p,q）位置的最短路徑；

---

思路：

• 首先，這道題的判斷條件為小明找到小紅，即tx=m,ty=n
• 接著，由于有四種方向，我們可以定義一個二維數組作為中間值，再對它進行加減來表示橫坐標和縱坐標

int next[4][2]={{0,1}, {1,0},{0,-1},{-1,0}};//順時針，右下左上 for(k=0;k<=3;k++) { tx=x+next[k][0]; ty=y+next[k][1]; }

• 在這之后，我們設置二維數組rub[][]來記錄是否有障礙，用二維數組record[][]來記錄該位置是否被走過

---

代碼：

#include<stdio.h> int record[51][51],rub[51][51]; int n,m,p,q,min=100000;int next[4][2]={{0,1}, {1,0},{0,-1},{-1,0}}; void search(int x,int y,int step) { int tx,ty,k;if(x==p&&y==q)//上一個dfs()函數傳過來的坐標，做了這個dfs()函數的形參 { if(step<min){min=step;} return ;//返回上一級函數 }for(k=0;k<=3;k++){ tx=x+next[k][0]; ty=y+next[k][1];if(tx<1 || tx>n || ty<1 || ty>m)//判斷是否越界 {continue; } if(rub[tx][ty]==0 && record[tx][ty]==0){record[tx][ty]=1; search(tx,ty,step+1); record[tx][ty]=0; } }return ; //返回上一級函數 } int main(){int i,j,startx,starty;scanf("%d %d",&n,&m);//迷宮大小 for(i=1;i<=n;i++){for(j=1;j<=m;j++){scanf("%d",&rub[i][j]); //迷宮形狀 } }scanf("%d%d",&startx,&starty); //小明的坐標 scanf("%d%d",&p,&q); //小紅的坐標 record[startx][starty]=1; search(startx,starty,0); printf("%d",min); return 0; }

---

運行結果：

---

注：

dfs常用在圖和數的搜索問題上，對于最短路徑問題，dfs并不是最優解法，所以我打算在學完樹和圖之后再回過來對dfs進行深度學習

總結

以上是生活随笔為你收集整理的dfs讲解+3例题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。