-肆行无忌网

发布时间：2025-06-24 19:52:41 作者：北方职教升学中心阅读量：151

在图的遍历中，DFS 从一个起始节点开始，标记该节点为已访问，然后遍历该节点的所有邻居。

总之，DFS 在不同的数据结构中有着广泛的应用，可以帮助我们解决各种复杂的问题。

🏳️‍🌈四、右）是否可行。通过这种方式，我们可以确保图中的每个节点都被访问到。例如，给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。迭代实现使用显式栈来模拟递归的过程，每次从栈中取出一个节点，访问其邻居，并将未访问的邻居压入栈。
例如，对于一个有向无环图，DFS 可以用于拓扑排序，确定节点的线性排序。可以使用 DFS 遍历所有可能的放置方案，找到满足条件的解。在这个过程中，每次尝试在一个位置放置皇后，如果放置后不满足条件，则回溯到上一步重新尝试。具体实现可以通过递归或者迭代的方式进行。

👥总结

本篇博文对 深度优先搜索（DFS）做了一个较为详细的介绍，不知道对你有没有帮助呢

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

请添加图片描述

以下是使用 DFS 解决最大岛屿面积问题的 C++ 代码示例：

publicintmaxAreaOfIsland(int[][]grid){intmax =0;for(inti =0;i <grid.length;i++){for(intj =0;j <grid[0].length;j++){if(grid[i][j]==1){max =Math.max(dfs(i,j,grid),max);}}}returnmax;}publicintdfs(inti,intj,int[][]grid){if(i<0||i>=grid.length||j<0||j>=grid[0].length||grid[i][j]==0){return0;}grid[i][j]=0;intcount=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);returncount;}

在这段代码中，maxAreaOfIsland函数遍历二维矩阵，找到所有的陆地格子，并调用dfs函数计算每个岛屿的面积。通过对图进行 DFS，并在回溯时将节点加入到排序结果中，可以得到一个满足拓扑顺序的序列。DFS 的应用场景

❤️（一）路径发现
🧡（二）拓扑排序
💛（三）解决谜题和游戏
💚（四）连通性检测
💙（五）生成迷宫

🏳️‍🌈四、以图的遍历为例，递归函数接受当前节点、

然而，在遍历大图时，递归实现可能会导致栈溢出问题。

💛（三）解决谜题和游戏

在一些谜题和游戏中，DFS 也有广泛的应用。例如，在处理非常深的树或者大规模的图时，递归实现可能会因为栈溢出而失败。下、dfs函数使用递归的方式遍历与当前格子相邻的陆地格子，并将其标记为已访问，最后返回岛屿的面积

另外，我们还可以使用方向数组的方式来实现 DFS，代码如下：

int[][]dirs =newint[][]{{-1,0},{1,0},{0,-1},{0,1}};voiddfs(int[][]grid,inti,intj,boolean[]visited){intm =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){intnext_i =i +d[0];intnext_j =j +d[1];dfs(grid,next_i,next_j,visited);}}

这种写法使用方向数组来处理上下左右的遍历，更加简洁和方便。这是因为递归调用会在栈上分配空间，当递归深度过大时，栈空间可能会耗尽。拓扑排序的目标是将图中的节点按照依赖关系进行排序，使得对于任意一条有向边 (u, v)，节点 u 在排序后的序列中出现在节点 v 之前。然后，在循环中，不断从栈中取出节点进行访问。例如，在任务调度问题中，每个任务可能依赖于其他任务的完成，使用拓扑排序可以确定任务的执行顺序，确保所有任务能够按照正确的顺序完成。

以下是使用 DFS 解决朋友圈问题的 C++ 代码示例：

classSolution{public:intfindCircleNum(vector<vector<int>>&M){intn=M.size(),cnt=0;vector<bool>vis(n,false);for(inti=0;i<n;i++){if(!vis[i]){dfs(M,vis,i);++cnt;}}returncnt;}voiddfs(vector<vector<int>>&M,vector<bool>&vis,intu){vis[u]=true;intm=M[u].size();for(inti=0;i<m;i++){if(M[u][i]==1&&!vis[i])dfs(M,vis,i);}}};

在这段代码中，findCircleNum函数遍历所有学生，如果当前学生未被访问，则调用dfs函数进行深度优先搜索，将与当前学生互为朋友的学生标记为已访问，并增加朋友圈数量。具体实现可以通过递归或者迭代的方式进行。

在二叉树的遍历中，DFS 可以用于前序、例如，在网络拓扑结构中，我们可以使用 DFS 来检测网络中的节点是否都能够相互通信。例如，在处理复杂的图结构时，我们可以根据需要对栈的操作进行优化，以提高遍历的效率。从起点开始，使用 DFS 不断尝试向四个方向移动，直到找到终点或者遍历完所有可能的路径。这种方式可以确保图中的每个节点都被访问到，并且可以用于检测图的连通性、例如，在一个二维迷宫中，我们可以将迷宫看作一个图，每个格子是一个节点，相邻的格子之间有边连接。如果可行，则继续向该方向进行深度优先搜索，直到找到终点或者无法继续前进。中序、DFS(i,c -1,matrix,toAt,Integer.MIN_VALUE);//遍历最后一列}for(inti =0;i <c;i++){DFS(0,i,matrix,toPa,Integer.MIN_VALUE);//遍历第一行DFS(r -1,i,matrix,toAt,Integer.MIN_VALUE);//遍历最后一行}for(inti =0;i <r;i++){for(intj =0;j <c;j++){if(toPa[i][j]&&toAt[i][j]){List<Integer>cur =newArrayList<>();cur.add(i);cur.add(j);res.add(cur);}}}returnres;}int[][]directions =newint[][]{{0,1},{0,-1},{-1,0},{1,0}};publicvoidDFS(intr,intc,int[][]matrix,boolean[][]toSea,intheight){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，分别表示能够流到太平洋和大西洋的格子。比如八皇后问题，要求在一个 8x8 的棋盘上放置 8 个皇后，使得它们不能相互攻击。如果邻居未被访问，则继续对该邻居进行深度优先搜索。DFS函数使用递归的方式遍历与当前格子相邻的格子，并将能够流到相应海洋的格子标记为true。它可以处理大规模的图，并且可以更好地控制遍历的过程。这种方式使得代码逻辑直观，对于小型图或者树的遍历非常高效。具体来说，我们从太平洋和大西洋的边界开始，使用 DFS 遍历与其相邻的格子，如果格子的高度不小于当前格子的高度，则可以流向该格子。以下是使用递归方式实现二叉树的前序、

💚（四）连通性检测

对于一个图，DFS 可以用于检测其连通性。inOrderRecur函数和postOrderRecur函数分别用于实现二叉树的前序、这些函数使用递归的方式遍历二叉树中的节点，并输出节点的值。DFS 的应用场景

❤️（一）路径发现

在迷宫问题中，DFS 可以用于寻找从起点到终点的路径。然后，我们继续遍历其他未被访问过的陆地格子，找到最大的岛屿面积。在这个过程中，我们可以记录下路径上的节点，以便在找到终点后回溯得到完整的路径。在这个过程中，我们可以记录下路径，从而生成一个迷宫。DFS 的具体应用示例

❤️（一）迷宫问题
🧡（二）岛屿问题
💛（三）朋友圈问题
💚（四）大洋流水问题
💙（五）图的遍历

👥总结

🏳️‍🌈一、

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

在这里插入图片描述

文章目录

🏳️‍🌈一、我们可以使用 DFS 算法来计算所有学生中的已知的朋友圈总数。后序遍历，帮助我们更好地理解树的结构和性质。
🏳️‍🌈二、
在迭代实现中，我们首先创建一个栈和一个访问标记数组。递归实现利用函数调用栈隐式地进行回溯，代码结构清晰，易于理解和实现。如果取出的节点尚未访问，则访问该节点，并将其邻居节点压入栈中。
总之，DFS 是一种强大的算法，在 C++ 编程中有着广泛的应用，可以帮助我们解决各种复杂的问题。中序和后序遍历。如果网络是连通的，那么从任何一个节点发送的数据都可以到达其他所有节点；如果网络不连通，则需要采取相应的措施来确保数据的传输。左、DFS 的具体应用示例
❤️（一）迷宫问题
在解决迷宫问题时，我们可以使用 DFS 来寻找从起点到终点的路径。DFS 的实现方式![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/438eeca6ac484931aa08b1acb54129d2.png =600x)
- ❤️（一）递归实现
- 🧡（二）迭代实现
🏳️‍🌈三、
以下是使用递归方式遍历无向图的 C++ 代码示例：
```
classundigraph{public:voidDFS(intv){cout <<"顶点"<<v <<"被访问!"<<endl;visited[v]=true;for(intprev =smallestadjvertex(v);prev >=0;prev =nextadjvertex(v,prev)){if(visited[prev]==false){DFS(prev);}}}intsmallestadjvertex(intv){for(inti =0;i <vertexnum;i++){if(adjmatrix[v][i]==1){returni;}return-1;}}intnextadjvertex(intv,intprev){for(inti =prev +1;i <vertexnum;i++){if(adjmatrix[v][i]==1){returni;}return-1;}}voidDFStraverse(){for(inti =0;i <vertexnum;i++){visited[i]=false;}for(inti =0;i <vertexnum;i++){if(visited[i]==false){DFS(i);}}}private:boolvisited[maxsize];intadjmatrix[maxsize][maxsize];intvertexnum;};
```
在这段代码中，undigraph类表示无向图，其中DFS函数使用递归的方式遍历无向图中的节点，smallestadjvertex函数和nextadjvertex函数分别用于寻找当前节点的最小序号邻接顶点和下一个邻接顶点，DFStraverse函数用于遍历整个无向图。
💙（五）生成迷宫
DFS 可以用于生成随机迷宫。
💙（五）图的遍历
以无向图和二叉树的遍历为例，展示 DFS 在不同数据结构中的具体实现。
💚（四）大洋流水问题
在大洋流水问题中，我们可以从大洋开始向上流，利用 DFS 确定能流到太平洋和大西洋的位置。据统计，通过 DFS 可以在合理的时间内找到八皇后问题的所有 92 组解。
DFS 的工作方式类似于在迷宫中探索，一旦进入一个通道，就尽可能地沿着这个通道走到底，直到遇到死胡同或者已经没有未访问的分支，然后再回溯到上一个岔路口，尝试其他路径。这种方式不依赖于函数调用栈，因此可以处理深度较大的图而不会出现栈溢出问题。
与递归实现相比，迭代实现的代码较为冗长，但更加健壮。形象地说，DFS 就像是一个勇敢的探险家，不断深入未知领域，只有在走投无路时才会回头寻找其他可能性。例如，使用 DFS 生成一个 10x10 的迷宫，通常可以在几毫秒内完成。具体来说，我们从一个陆地格子开始，使用 DFS 遍历与其相邻的陆地格子，并记录遍历过的格子数量，即为该岛屿的面积。例如，在解决迷宫问题时，我们可以用一个二维数组模拟平面，用一个数组记录坐标是否被访问过，然后从起点开始，使用 DFS 算法不断尝试向四个方向移动，直到找到终点或者遍历完所有可能的路径。
例如，以下是使用递归方式解决迷宫问题的 C++ 代码示例：
```
#include<iostream>#include<vector>constintN =10;// 迷宫尺寸intmaze[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;// 存储路径booldfs(intx,inty){// 深度优先搜索if(x <0||x >=N ||y <0||y >=N)returnfalse;// 超出边界if(maze[x][y]==1)returnfalse;// 遇到墙if(x ==N -1&&y ==N -1){// 到达终点path.emplace_back(x,y);returntrue;}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)){// 沿四个方向搜索returntrue;}path.pop_back();// 回溯returnfalse;}intmain(){dfs(1,1);// 从起点开始搜索if(path.empty()){std::cout <<"No path found."<<std::endl;}else{std::cout <<"Path:"<<std::endl;for(constauto&p :path){std::cout <<"(" <<p.first <<"," <<p.second <<")" <<std::endl;}}return0;}
```
这段代码中，dfs函数使用递归的方式在迷宫中进行深度优先搜索，找到从起点到终点的路径。
在 C++ 中，DFS 可以通过递归或者显式栈来实现。据实际测试，对于一个中等规模的迷宫（如 10x10 的迷宫），DFS 可以在较短的时间内找到路径。中序和后序遍历的 C++ 代码示例：
```
structTreeNode{intval;TreeNode *left;TreeNode *right;TreeNode(intx):val(x),left(NULL),right(NULL){}};voidpreOrderRecur(TreeNode *root){if(!root)return;cout <<root->val <<" ";preOrderRecur(root->left);preOrderRecur(root->right);}voidinOrderRecur(TreeNode *root){if(!root)return;inOrderRecur(root->left);cout <<root->val <<" ";inOrderRecur(root->right);}voidpostOrderRecur(TreeNode *root){if(!root)return;postOrderRecur(root->left);postOrderRecur(root->right);cout <<root->val <<" ";}
```
在这段代码中，TreeNode结构体表示二叉树的节点，preOrderRecur函数、从图中的任意一个节点开始进行 DFS，如果能够访问到图中的所有节点，则说明该图是连通的；否则，图是不连通的。将起始节点压入栈中，并标记为已访问。寻找路径等问题。同时，我们可以使用一个栈或者向量来保存探索过程中的坐标，以便在找到终点后回溯得到完整的路径。以递归方式为例，我们从一个起始节点开始，标记该节点为已访问，然后遍历该节点的所有邻居节点。以递归方式为例，我们从起点开始，检查当前位置的四个方向（上、中序和后序遍历。其核心原理是从起始顶点开始，沿着路径尽可能深地探索，直到无法继续前进时才回溯。如果没有找到路径，则输出 “No path found.”。
🧡（二）岛屿问题
以最大岛屿面积问题为例，我们可以使用 DFS 在二维矩阵中解决这个问题。一种常见的方法是从一个随机的起点开始，不断地随机选择一个未访问的相邻节点进行扩展，直到无法继续扩展为止。在搜索过程中，我们可以使用一个二维数组来记录已经访问过的位置，以避免重复访问。
以下是使用 DFS 解决大洋流水问题的 C++ 代码示例：
```
classSolution{public:List<List<Integer>>pacificAtlantic(int[][]matrix){List<List<Integer>>res =newArrayList<>();if(matrix.length ==0||matrix[0].length ==0){returnres;}intr =matrix.length;//行数，可以看成 y 轴intc =matrix[0].length;//列数，可以看成 x 轴boolean[][]toPa =newboolean[r][c];boolean[][]toAt =newboolean[r][c];for(inti =0;i <r;i++){DFS(i,0,matrix,toPa,Integer.MIN_VALUE);//遍历第一列，即正方形的左边，它用 DFS 来遍历哪些能够通过它，到达太平洋（Pa）的水流。dfs函数使用递归的方式遍历与当前学生互为朋友的学生，并将其标记为已访问。
🧡（二）拓扑排序
在有向无环图中，DFS 可以用于拓扑排序。如果 M [i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。据统计，在一些实际应用中，当图的节点数超过一定数量（如几万甚至更多）时，递归实现的 DFS 就有可能出现栈溢出问题。DFS 的实现方式
```

❤️（一）递归实现

在 C++ 中，使用递归实现 DFS 具有简洁易懂的特点。生成的迷宫具有随机性和复杂性，可以用于游戏开发或者算法测试。在树的遍历中，DFS 可以用于前序、
在无向图的遍历中，我们可以使用 DFS 来遍历图中的所有节点。DFS 的基础概念

深度优先搜索（DFS）是一种用于遍历或搜索树或图数据结构的算法。然后，从太平洋和大西洋的边界开始，使用 DFS 遍历与其相邻的格子，并将能够流到相应海洋的格子标记为true。图的邻接表和访问标记数组为参数，首先标记当前节点为已访问，然后遍历当前节点的所有邻居节点。

💛（三）朋友圈问题

在求解朋友圈数量问题中，我们可以使用 DFS 来体现其在传递关系问题中的作用。

学生姓名：
男女
联系电话：
意向班型：
我是学生我是家长

咨询热线：	400-029-7969
咨询电话：	029-61855169 029-61855069
学校邮箱：	bfzx365@163.com
学校地址：	西安市雁塔区长安西路66号

👥总结

💛（三）解决谜题和游戏

💚（四）连通性检测

❤️（一）路径发现

文章目录

❤️（一）迷宫问题

💙（五）生成迷宫

💙（五）图的遍历

💚（四）大洋流水问题

🧡（二）岛屿问题

🧡（二）拓扑排序

`❤️（一）递归实现`

`💛（三）朋友圈问题`

🧡（二）迭代实现