📢博客主页：https://blog.csdn.net/2301_779549673
📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正！
📢本文由 JohnKi 原创，首发于 CSDN🙉
📢未来很长，值得我们全力奔赴更美好的生活✨

---

🏳️‍🌈一、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） 做了一个较为详细的介绍，不知道对你有没有帮助呢

觉得博主写得还不错的三连支持下吧！会继续努力的~