?博客主页：https://blog.csdn.net/2301_779549673
?欢迎点赞 ? 收藏 ⭐留言 ? 如有错误敬请指正！
?本文由 JohnKi 原创，首发于 CSDN?
?未来很长，值得我们全力奔赴更美好的生活✨
文章目录
?️?一、DFS 的基础概念?️?二、DFS 的实现方式❤️（一）递归实现?（二）迭代实现 ?️?三、DFS 的应用场景❤️（一）路径发现?（二）拓扑排序?（三）解决谜题和游戏?（四）连通性检测?（五）生成迷宫 ?️?四、DFS 的具体应用示例❤️（一）迷宫问题?（二）岛屿问题?（三）朋友圈问题?（四）大洋流水问题?（五）图的遍历 ?总结
?️?一、DFS 的基础概念
深度优先搜索（DFS）是一种用于遍历或搜索树或图数据结构的算法。其核心原理是从起始顶点开始，沿着路径尽可能深地探索，直到无法继续前进时才回溯。
DFS 的工作方式类似于在迷宫中探索，一旦进入一个通道，就尽可能地沿着这个通道走到底，直到遇到死胡同或者已经没有未访问的分支，然后再回溯到上一个岔路口，尝试其他路径。形象地说，DFS 就像是一个勇敢的探险家，不断深入未知领域，只有在走投无路时才会回头寻找其他可能性。
在 C++ 中，DFS 可以通过递归或者显式栈来实现。例如，在解决迷宫问题时，我们可以用一个二维数组模拟平面，用一个数组记录坐标是否被访问过，然后从起点开始，使用 DFS 算法不断尝试向四个方向移动，直到找到终点或者遍历完所有可能的路径。
在图的遍历中，DFS 从一个起始节点开始，标记该节点为已访问，然后遍历该节点的所有邻居。如果邻居未被访问，则继续对该邻居进行深度优先搜索。这种方式可以确保图中的每个节点都被访问到，并且可以用于检测图的连通性、寻找路径等问题。
例如，对于一个有向无环图，DFS 可以用于拓扑排序，确定节点的线性排序。在树的遍历中，DFS 可以用于前序、中序、后序遍历，帮助我们更好地理解树的结构和性质。
总之，DFS 是一种强大的算法，在 C++ 编程中有着广泛的应用，可以帮助我们解决各种复杂的问题。
?️?二、DFS 的实现方式
❤️（一）递归实现
在 C++ 中，使用递归实现 DFS 具有简洁易懂的特点。递归实现利用函数调用栈隐式地进行回溯，代码结构清晰，易于理解和实现。以图的遍历为例，递归函数接受当前节点、图的邻接表和访问标记数组为参数，首先标记当前节点为已访问，然后遍历当前节点的所有邻居节点。如果邻居节点尚未访问，则递归地进行深度优先搜索。这种方式使得代码逻辑直观，对于小型图或者树的遍历非常高效。
然而，在遍历大图时，递归实现可能会导致栈溢出问题。这是因为递归调用会在栈上分配空间，当递归深度过大时，栈空间可能会耗尽。例如，在处理非常深的树或者大规模的图时，递归实现可能会因为栈溢出而失败。据统计，在一些实际应用中，当图的节点数超过一定数量（如几万甚至更多）时，递归实现的 DFS 就有可能出现栈溢出问题。
?（二）迭代实现
使用栈进行迭代实现 DFS 可以避免在深度较大的图中出现栈溢出风险。迭代实现使用显式栈来模拟递归的过程，每次从栈中取出一个节点，访问其邻居，并将未访问的邻居压入栈。这种方式不依赖于函数调用栈，因此可以处理深度较大的图而不会出现栈溢出问题。
在迭代实现中，我们首先创建一个栈和一个访问标记数组。将起始节点压入栈中，并标记为已访问。然后，在循环中，不断从栈中取出节点进行访问。如果取出的节点尚未访问，则访问该节点，并将其邻居节点压入栈中。通过这种方式，我们可以确保图中的每个节点都被访问到。
与递归实现相比，迭代实现的代码较为冗长，但更加健壮。它可以处理大规模的图，并且可以更好地控制遍历的过程。例如，在处理复杂的图结构时，我们可以根据需要对栈的操作进行优化，以提高遍历的效率。
?️?三、DFS 的应用场景
❤️（一）路径发现
在迷宫问题中，DFS 可以用于寻找从起点到终点的路径。例如，在一个二维迷宫中，我们可以将迷宫看作一个图，每个格子是一个节点，相邻的格子之间有边连接。从起点开始，使用 DFS 不断尝试向四个方向移动，直到找到终点或者遍历完所有可能的路径。在这个过程中，我们可以记录下路径上的节点，以便在找到终点后回溯得到完整的路径。据实际测试，对于一个中等规模的迷宫（如 10x10 的迷宫），DFS 可以在较短的时间内找到路径。
?（二）拓扑排序
在有向无环图中，DFS 可以用于拓扑排序。拓扑排序的目标是将图中的节点按照依赖关系进行排序，使得对于任意一条有向边 (u, v)，节点 u 在排序后的序列中出现在节点 v 之前。通过对图进行 DFS，并在回溯时将节点加入到排序结果中，可以得到一个满足拓扑顺序的序列。例如，在任务调度问题中，每个任务可能依赖于其他任务的完成，使用拓扑排序可以确定任务的执行顺序，确保所有任务能够按照正确的顺序完成。
?（三）解决谜题和游戏
在一些谜题和游戏中，DFS 也有广泛的应用。比如八皇后问题，要求在一个 8x8 的棋盘上放置 8 个皇后，使得它们不能相互攻击。可以使用 DFS 遍历所有可能的放置方案，找到满足条件的解。在这个过程中，每次尝试在一个位置放置皇后，如果放置后不满足条件，则回溯到上一步重新尝试。据统计，通过 DFS 可以在合理的时间内找到八皇后问题的所有 92 组解。
?（四）连通性检测
对于一个图，DFS 可以用于检测其连通性。从图中的任意一个节点开始进行 DFS，如果能够访问到图中的所有节点，则说明该图是连通的；否则，图是不连通的。例如，在网络拓扑结构中，我们可以使用 DFS 来检测网络中的节点是否都能够相互通信。如果网络是连通的，那么从任何一个节点发送的数据都可以到达其他所有节点；如果网络不连通，则需要采取相应的措施来确保数据的传输。
?（五）生成迷宫
DFS 可以用于生成随机迷宫。一种常见的方法是从一个随机的起点开始，不断地随机选择一个未访问的相邻节点进行扩展，直到无法继续扩展为止。在这个过程中，我们可以记录下路径，从而生成一个迷宫。例如，使用 DFS 生成一个 10x10 的迷宫，通常可以在几毫秒内完成。生成的迷宫具有随机性和复杂性，可以用于游戏开发或者算法测试。
?️?四、DFS 的具体应用示例
❤️（一）迷宫问题
在解决迷宫问题时，我们可以使用 DFS 来寻找从起点到终点的路径。具体实现可以通过递归或者迭代的方式进行。以递归方式为例，我们从起点开始，检查当前位置的四个方向（上、下、左、右）是否可行。如果可行，则继续向该方向进行深度优先搜索，直到找到终点或者无法继续前进。在搜索过程中，我们可以使用一个二维数组来记录已经访问过的位置，以避免重复访问。同时，我们可以使用一个栈或者向量来保存探索过程中的坐标，以便在找到终点后回溯得到完整的路径。
例如，以下是使用递归方式解决迷宫问题的 C++ 代码示例：
#include<iostream>#include<vector>const int N = 10; // 迷宫尺寸int maze[N][N] = { // 迷宫地图，1表示墙，0表示通道{1,1, 1, 1, 1, 1, 1, 1, 1, 1},{1,0, 0, 0, 1, 0, 0, 0, 0, 1},{1,0, 1, 0, 1, 0, 1, 1, 0, 1},{1,0, 0, 1, 0, 0, 0, 0, 0, 1},{1,0, 1, 0, 0, 1, 0, 1, 0, 1},{1,0, 0, 0, 1, 0, 0, 0, 0, 1},{1,0, 1, 0, 1, 0, 1, 0, 1, 1},{1,0, 0, 0, 0, 0, 0, 0, 0, 1},{1,0, 1, 0, 1, 0, 1, 1, 0, 1},{1,1, 1, 1, 1, 1, 1, 1, 1, 1}};std::vector<std::pair<int, int>> path; // 存储路径bool dfs(int x, int y){ // 深度优先搜索 if (x <0 || x >= N || y < 0 || y >= N) return false; // 超出边界 if (maze[x][y] ==1) return false; // 遇到墙 if (x == N -1 && y == N - 1) { // 到达终点 path.emplace_back(x, y); return true; } maze[x][y] = 1; // 标记已访问 path.emplace_back(x, y); // 存储路径 if (dfs(x+1, y) || dfs(x-1, y) || dfs(x, y+1) || dfs(x, y-1)) { // 沿四个方向搜索 return true; } path.pop_back(); // 回溯 return false;}int main(){ dfs(1,1); // 从起点开始搜索 if (path.empty()) { std::cout << "No path found." << std::endl; } else { std::cout << "Path:" << std::endl; for (const auto& p : path) { std::cout << "(\" << p.first << \", \" << p.second << \")\" << std::endl; } } return 0;}这段代码中，dfs函数使用递归的方式在迷宫中进行深度优先搜索，找到从起点到终点的路径。如果找到了路径，则将路径中的坐标存储在path向量中，并在主函数中输出路径。如果没有找到路径，则输出 “No path found.”。
?（二）岛屿问题
以最大岛屿面积问题为例，我们可以使用 DFS 在二维矩阵中解决这个问题。具体来说，我们从一个陆地格子开始，使用 DFS 遍历与其相邻的陆地格子，并记录遍历过的格子数量，即为该岛屿的面积。然后，我们继续遍历其他未被访问过的陆地格子，找到最大的岛屿面积。
以下是使用 DFS 解决最大岛屿面积问题的 C++ 代码示例：
public int maxAreaOfIsland(int[][] grid) { int max = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j]==1) { max = Math.max(dfs(i, j, grid), max); } } } return max;}public int dfs(int i,int j,int[][] grid) { if (i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==0) { return 0; } grid[i][j]=0; int count=1; count+=dfs(i+1, j, grid); count+=dfs(i-1, j, grid); count+=dfs(i, j+1, grid); count+=dfs(i, j-1, grid); return count;}在这段代码中，maxAreaOfIsland函数遍历二维矩阵，找到所有的陆地格子，并调用dfs函数计算每个岛屿的面积。dfs函数使用递归的方式遍历与当前格子相邻的陆地格子，并将其标记为已访问，最后返回岛屿的面积
另外，我们还可以使用方向数组的方式来实现 DFS，代码如下：
int[][] dirs = new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}};void dfs(int[][] grid, int i, int j, boolean[] visited) { int m = grid.length, n = grid[0].length; if (i <0 || j < 0 || i >= m || j >= n) { return; } if (visited[i][j]) { return; } visited[i][j] = true; for (int[] d : dirs) { int next_i = i + d[0]; int next_j = j + d[1]; dfs(grid, next_i, next_j, visited); }}这种写法使用方向数组来处理上下左右的遍历，更加简洁和方便。
?（三）朋友圈问题
在求解朋友圈数量问题中，我们可以使用 DFS 来体现其在传递关系问题中的作用。例如，给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果 M [i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。我们可以使用 DFS 算法来计算所有学生中的已知的朋友圈总数。
以下是使用 DFS 解决朋友圈问题的 C++ 代码示例：
class Solution{public: int findCircleNum(vector<vector<int>>& M) { int n=M.size(),cnt=0; vector<bool>vis(n,false); for(int i=0;i<n;i++){ if(!vis[i]){ dfs(M,vis,i); ++cnt; } } return cnt; } void dfs(vector<vector<int>>& M,vector<bool>& vis,int u){ vis[u]=true; int m=M[u].size(); for(int i=0;i<m;i++){ if(M[u][i]==1&&!vis[i]) dfs(M,vis,i); } }};在这段代码中，findCircleNum函数遍历所有学生，如果当前学生未被访问，则调用dfs函数进行深度优先搜索，将与当前学生互为朋友的学生标记为已访问，并增加朋友圈数量。dfs函数使用递归的方式遍历与当前学生互为朋友的学生，并将其标记为已访问。
?（四）大洋流水问题
在大洋流水问题中，我们可以从大洋开始向上流，利用 DFS 确定能流到太平洋和大西洋的位置。具体来说，我们从太平洋和大西洋的边界开始，使用 DFS 遍历与其相邻的格子，如果格子的高度不小于当前格子的高度，则可以流向该格子。最后，我们遍历整个矩阵，找到既能流到太平洋又能流到大西洋的格子。
以下是使用 DFS 解决大洋流水问题的 C++ 代码示例：
class Solution{public: List<List<Integer>> pacificAtlantic(int[][] matrix) { List<List<Integer>> res = new ArrayList<>(); if (matrix.length == 0 || matrix[0].length == 0) { return res; } int r = matrix.length; //行数，可以看成 y 轴 int c = matrix[0].length; //列数，可以看成 x 轴 boolean[][] toPa = new boolean[r][c]; boolean[][] toAt = new boolean[r][c]; for (int i = 0; i < r; i++) { DFS(i, 0, matrix, toPa, Integer.MIN_VALUE); //遍历第一列，即正方形的左边，它用 DFS 来遍历哪些能够通过它，到达太平洋（Pa）的水流。 DFS(i, c - 1, matrix, toAt, Integer.MIN_VALUE); //遍历最后一列 } for (int i = 0; i < c; i++) { DFS(0, i, matrix, toPa, Integer.MIN_VALUE); //遍历第一行 DFS(r - 1, i, matrix, toAt, Integer.MIN_VALUE); //遍历最后一行 } for (int i = 0; i < r; i++) { for (int j = 0; j < c; j++) { if (toPa[i][j] && toAt[i][j]) { List<Integer> cur = new ArrayList<>(); cur.add(i); cur.add(j); res.add(cur); } } } return res; } int[][] directions = new int[][]{{0,1},{0,-1},{-1,0},{1,0}}; public void DFS(int r, int c, int[][] matrix, boolean[][] toSea, int height) { if (r < 0 || r >= matrix.length || c < 0 || c >= matrix[0].length || toSea[r][c] || matrix[r][c]< height) { return; } toSea[r][c]=true; for (int[] dir : directions) { DFS(r + dir[0], c + dir[1], matrix, toSea, matrix[r][c]); } }};在这段代码中，pacificAtlantic函数首先初始化两个布尔数组toPa和toAt，分别表示能够流到太平洋和大西洋的格子。然后，从太平洋和大西洋的边界开始，使用 DFS 遍历与其相邻的格子，并将能够流到相应海洋的格子标记为true。最后，遍历整个矩阵，找到既能流到太平洋又能流到大西洋的格子，并将其坐标加入结果列表中。DFS函数使用递归的方式遍历与当前格子相邻的格子，并将能够流到相应海洋的格子标记为true。
?（五）图的遍历
以无向图和二叉树的遍历为例，展示 DFS 在不同数据结构中的具体实现。
在无向图的遍历中，我们可以使用 DFS 来遍历图中的所有节点。具体实现可以通过递归或者迭代的方式进行。以递归方式为例，我们从一个起始节点开始，标记该节点为已访问，然后遍历该节点的所有邻居节点。如果邻居节点尚未访问，则递归地进行深度优先搜索。
以下是使用递归方式遍历无向图的 C++ 代码示例：
class undigraph {public: void DFS(int v) { cout << "顶点" << v << "被访问!" << endl; visited[v] = true; for (int prev = smallestadjvertex(v); prev >= 0; prev = nextadjvertex(v, prev)) { if (visited[prev] == false) { DFS(prev); } } } int smallestadjvertex(int v) { for (int i = 0; i < vertexnum; i++) { if (adjmatrix[v][i] == 1) { return i; } return -1; } } int nextadjvertex(int v, int prev) { for (int i = prev + 1; i < vertexnum; i++) { if (adjmatrix[v][i] == 1) { return i; } return -1; } } void DFStraverse() { for (int i = 0; i < vertexnum; i++) { visited[i] = false; } for (int i = 0; i < vertexnum; i++) { if (visited[i] == false) { DFS(i); } } }private: bool visited[maxsize]; int adjmatrix[maxsize][maxsize]; int vertexnum;};在这段代码中，undigraph类表示无向图，其中DFS函数使用递归的方式遍历无向图中的节点，smallestadjvertex函数和nextadjvertex函数分别用于寻找当前节点的最小序号邻接顶点和下一个邻接顶点，DFStraverse函数用于遍历整个无向图。
在二叉树的遍历中，DFS 可以用于前序、中序和后序遍历。以下是使用递归方式实现二叉树的前序、中序和后序遍历的 C++ 代码示例：
struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {}};void preOrderRecur(TreeNode *root) { if (!root) return; cout << root->val << " "; preOrderRecur(root->left); preOrderRecur(root->right);}void inOrderRecur(TreeNode *root) { if (!root) return; inOrderRecur(root->left); cout << root->val << " "; inOrderRecur(root->right);}void postOrderRecur(TreeNode *root) { if (!root) return; postOrderRecur(root->left); postOrderRecur(root->right); cout << root->val << " ";}在这段代码中，TreeNode结构体表示二叉树的节点，preOrderRecur函数、inOrderRecur函数和postOrderRecur函数分别用于实现二叉树的前序、中序和后序遍历。这些函数使用递归的方式遍历二叉树中的节点，并输出节点的值。
总之，DFS 在不同的数据结构中有着广泛的应用，可以帮助我们解决各种复杂的问题。
?总结
本篇博文对 深度优先搜索（DFS） 做了一个较为详细的介绍，不知道对你有没有帮助呢
觉得博主写得还不错的三连支持下吧！会继续努力的~
