深度优先算法DFS（Depth First Search）

大家好，欢迎来到IT知识分享网。

一、基本思想

     不撞南墙不回头

1. 为了求得问题的解，先选择某一种可能情况向前探索；
2. 在探索过程中，一旦发现原来的选择是错误的，就退回一步重新选择，继续向前探索；
3. 如此反复进行，直至得到解或证明无解。

二、算法原理 

深度优先搜索（Depth First Search），是图遍历算法的一种。用一句话概括就是：“一直往下走，走不通回头，换条路再走，直到无路可走”。

假设我们有一个二叉树，共有10个节点，以下是DFS的简单示范：

从根节点开始向下搜索

然后搜索到2号节点

 继续不断向深层处的节点搜索，搜索到4号节点

最后搜索到7号节点

当搜索到7号节点后，我们发现无路可走了，因为7号节点是当前这条路径下最深处的节点，因此，我们需要进行回溯操作

 当回溯到4号节点时，我们发现4号节点并没有另一条路，也就是说从4号节点向下搜索的话，只能搜索到7号节点，但是可是刚刚才从7号节点回溯上来诶，我们总不可能又搜索到7号，然后又回溯到4号无限下去吧……所以，我们得再次回溯，也就是跳到2号节点上。

 当再次跳到2号节点上时，我们发现从2号节点开始，还有另一条路可以走。那我们就走下去！

此时又有两条路可以走，我们先去往8号

走到8号，我们发现又走到头了，那就再对它使用回溯吧！！！ 

这次我们选择另一条路，走到9号

 然后我们发现又双走到头了，因此，再次回溯，从9号跳到5号，再跳到2号，然后再跳到1号(因为5号，2号向下的路我们已经走过了，但我们发现1号节点向下的路还有一条是我们没走过的)

接下来搜索类似，我们走到3号，然后走到6号，然后走到10号

当10号走完后，这颗树的每个节点都被搜索过了，最后回溯到根节点

三、模板

1、C模板

int a[510]; //存储每次选出来的数据 int book[510]; //标记是否被访问 int ans = 0; //记录符合条件的次数 void DFS(int cur){ if(cur == k){ //k个数已经选完，可以进行输出等相关操作 for(int i = 0; i < cur; i++){ printf("%d ", a[i]); } ans++; return ; } for(int i = 0; i < n; i++){ //遍历 n个数，并从中选择k个数 if(!book[i]){ //若没有被访问 book[i] = 1; //标记已被访问 a[cur] = i; //选定本数，并加入数组 DFS(cur + 1); //递归，cur+1 book[i] = 0; //释放，标记为没被访问，方便下次引用 } } } 

2、C++模板

vector<int> a; // 记录每次排列 vector<int> book; //标记是否被访问 void DFS(int cur, int k, vector<int>& nums){ if(cur == k){ //k个数已经选完，可以进行输出等相关操作 for(int i = 0; i < cur; i++){ printf("%d ", a[i]); } return ; } for(int i = 0; i < k; i++){ //遍历 n个数，并从中选择k个数 if(book[nums[i]] == 0){ //若没有被访问 a.push_back(nums[i]); //选定本输，并加入数组 book[nums[i]] = 1; //标记已被访问 DFS(cur + 1, n, nums); //递归，cur+1 book[nums[i]] = 0; //释放，标记为没被访问，方便下次引用 a.pop_back(); //弹出刚刚标记为未访问的数 } } } 

四、例题（持续更新）

例题一（全排列）

1、思路：

2、代码：

#include<bits/stdc++.h> using namespace std; int n, res[14]; int book[14] = { 0 }; void DFS(int k) { if (k > n) { for (int i = 1; i <= n; i++) { cout << setiosflags(ios::right) << setw(5) << res[i];//注意控制输出格式 } cout << endl; return; } for (int j = 1; j <= n; j++) { if (!book[j]) { res[k] = j; book[j] = 1; DFS(k+1); book[j] = 0; } } } int main() { cin >> n; DFS(1); return 0; }

例题二（无向图）

1、思路：

这道题可以看做裸的邻接矩阵存储+dfs遍历，没有什么特殊的点

有路就走，走过的不再走，记录最大的长度

需要注意的是 无向图要把横纵坐标反过来再次保存

2、代码：

#include<bits/stdc++.h> #define N 25 using namespace std; int n, m; int mp[N][N] = { 0 }; int book[N] = { 0 };//记录是否走过 int nowOne, nextOne, length; int res = 0; void dfs(int nowDFS, int nowLength) { res = max(res, nowLength); for (int j = 1; j <= n; j++) { if (mp[nowDFS][j] && !book[j]) { book[nowDFS] = 1; dfs(j, nowLength+ mp[nowDFS][j]); book[nowDFS] = 0; } } return; } int main() { cin >> n >> m; for (int i = 0; i < m; i++) { cin >> nowOne >> nextOne >> length; mp[nowOne][nextOne] = length; mp[nextOne][nowOne] = length; } for (int i = 1; i <= n; i++) { dfs(i, 0); } cout << res; return 0; }

例题三（李白打酒加强版）

1、思路

记忆化搜索

dp[st][shop][flower] st表示酒，shop表示剩下的店，flower表示剩下的花

dp[st][shop][flower] = (dfs(st * 2, shop – 1, flower) + dfs(st – 1, shop, flower – 1)) % MOD表示遇到店，店减去一，酒乘二，遇到花，花减一，酒减一，直到st == 1 && shop == 0 && flower == 1，即只剩一瓶酒和一个花没遇到的时候，搜索结束

记忆化需要记录搜索过的dp，并直接返回这个结果，不再进入搜索

2、代码

#include<bits/stdc++.h> #define MOD  using namespace std; int n, m; int dp[105][105][105]; int dfs(int st, int shop, int flower) { if (st < 0 || shop < 0 || flower < 0) { return 0; } if (st > flower) { return 0; } if (st == 1 && shop == 0 && flower == 1) { return 1; } if (dp[st][shop][flower] != -1) { return dp[st][shop][flower]; //记忆化搜索：搜索过的就直接跳过 } dp[st][shop][flower] = (dfs(st * 2, shop - 1, flower) + dfs(st - 1, shop, flower - 1)) % MOD; return dp[st][shop][flower]; } int main() { memset(dp, -1, sizeof dp); cin >> n >> m; cout << dfs(2, n, m); return 0; }

例题四（飞机降落）

1、思路 

这道题目要求我们判断给定的飞机是否都能在它们的油料耗尽之前降落。为了寻找是否存在合法的降落序列，我们可以使用深度优先搜索（DFS）的方法，尝试所有可能的降落顺序。

首先，我们需要理解题目中的条件。每架飞机在Ti时刻到达机场上空，剩余油料可以维持Di个单位时间，降落需要Li个单位时间。这意味着每架飞机可以在Ti到Ti+Di的时间段内开始降落。

然后，我们可以按照以下步骤来实现 DFS：

2、代码

#include<bits/stdc++.h> #define MAX  using namespace std; int T; int t[MAX], d[MAX], l[MAX]; bool book[MAX]; bool dfs(int num, int last, int n) { if (num == n) { return true; } else { for (int i = 1; i <= n; i++) { if (!book[i] && t[i] + d[i] >= last) { book[i] = true; if (dfs(num + 1, max(last, t[i]) + l[i], n)) { return true; } book[i] = false; } } } return false; } int main() { cin >> T; while (T--) { int n; cin >> n; memset(t, 0, sizeof t); memset(d, 0, sizeof d); memset(l, 0, sizeof l); memset(book, false, sizeof book); for (int i = 1; i <= n; i++) { cin >> t[i] >> d[i] >> l[i]; } if (dfs(0, 0, n)) { cout << "YES" << endl; } else { cout << "NO" << endl; } } return 0; }

 例题五（岛屿个数）

1、思路

在外围加上一圈海，然后先对海搜索，当遇到岛屿时，就对岛屿搜索，并记录一个岛屿数量

2、代码

#include <iostream> #include <vector> using namespace std; int deltaOfSea[8][2] = { 
  {-1, -1},{-1, 0},{-1, 1},{0, 1},{1, 1},{1, 0},{1, -1},{0, -1}}; int deltaOfIsland[4][2] = { 
  {-1, 0},{1, 0},{0, -1},{0, 1}}; int ans = 0; void DFS_Island(vector<vector<char>>& data, int r, int c, int m, int n){ data[r][c] = 'N'; for(int i = 0; i < 4; ++i){ int newR = r + deltaOfIsland[i][0]; int newC = c + deltaOfIsland[i][1]; if(newR >= 0 && newR < m && newC >= 0 && newC < n){ if(data[newR][newC] == '1') DFS_Island(data, newR, newC, m, n); } } } void DFS_Sea(vector<vector<char>>& data, int r, int c, int m, int n){ data[r][c] = 'N'; for(int i = 0; i < 8; ++i){ int newR = r + deltaOfSea[i][0]; int newC = c + deltaOfSea[i][1]; if(newR >= 0 && newR < m && newC >= 0 && newC < n){ if(data[newR][newC] == '1'){ DFS_Island(data, newR, newC, m, n); ++ans; } else if(data[newR][newC] == '0'){ DFS_Sea(data, newR, newC, m, n); } } } } int main() { int t; cin >> t; vector< vector<vector<char>> > datas; for(int i = 0; i < t; ++i){ int m, n; cin >> m >> n; vector<vector<char>> data(m + 2, vector<char>(n + 2, '0')); //扩展一圈0 for(int r = 1; r < m + 1; ++r){ for(int c = 1; c < n + 1; ++c){ cin >> data[r][c]; } } datas.push_back(data); } for(int i = 0; i < t; ++i){ vector<vector<char>> data = datas[i]; int m = data.size(); int n = data[0].size(); DFS_Sea(data, 0, 0, m, n); cout << ans << endl; ans = 0; } return 0; }