注意：本贴的所有代码都请勿抄袭，违者后果自负！
本帖的做头代码均为模版题的代码，作业中均无对应的题目
不是很简的简介
深度优先搜索（Depth-First Search, DFS）是一种用于遍历或搜索树或图的算法。在C++中实现深度优先搜索通常使用递归方法，但也可以使用栈来实现非递归版本。DFS算法沿着树的深度遍历树的节点，尽可能深地搜索树的分支。
基本思想
- 从一个节点开始，探索尽可能深的分支，直到达到叶子节点。
- 当节点v的所有出边都已被探寻过，搜索将回溯到发现节点v的那条边的起始节点。
- 这个过程一直进行到已发现从原始节点可达的所有节点为止。
实现步骤
- 选择起始节点：选择一个节点作为搜索的起始点。
- 访问节点：访问该节点，并标记该节点为已访问。
- 寻找邻接节点：查找当前节点的所有未被访问的邻接节点。
- 递归搜索：对每个未被访问的邻接节点，递归执行步骤2和3。
- 回溯：如果所有邻接节点都已被访问，回溯到上一个节点。
应用
深度优先搜索在许多领域有应用，包括：
- 路径搜索和求解
- 迷宫问题
- 图的连通性问题
- 拓扑排序
- 解决数独问题
- 网络爬虫
DFS是探索和理解图结构的基础算法之一。
下面是例题部分
例题1：迷宫解法
#include<bits/stdc++.h>
using namespace std;
void dfs(坐标x,坐标y){
if(找到目标点){
计数;
}
else{
for(遍历4个方向){
记录新位置;
if(新位置未被标记&&新位置没有越界&&新位置不是墙){
标记新位置;
dfs(新位置的坐标);
回溯,清除标记;
}
}
}
}
int main(){
dfs(起点坐标);
return 0;
}
例题2：洪水填充
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
char a[25][25];
bool vis[25][25];//标记数组
void f(int x,int y){
if() return;//判断条件是否合法，不合法就跳出
//标记位置
//能到的地方+1
//遍历四个方向
}
int main(){
memset(vis,false,sizeof(vis));
cin>>n>>m;
int sx,sy;
for(int i=1;i<=m;i++){
for(int j=1;j<=n;j++){
cin>>a[i][j];
//设置开始坐标
}
}
//开始递归
cout<<ans;//输出结果
return 0;
}
例题3：八连通
这也属于一个洪水填充问题，即遍历整个数组，发现有空地就把连通的空地都填充起来，最后看一下填充了几片空地
#include<bits/stdc++.h>
using namespace std;
int n,m;
int ans=0;
char a[105][105];
//两个方向数组
bool jc(int x,int y){ //判断边界是否合法的函数
}
void dfs(int x,int y){
if() return; //判断当前位置
//标记当前位置
for(int i=0;i<8;i++){//遍历8个方向
int nx=x+dx[i];//计算新位置
int ny=y+dy[i];
if ){//检查
//递归
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
if(a[i][j]=='W'){
dfs(i,j);
ans++;
}
}
}
cout<<ans;
return 0;
}
创作不易，点个赞吧
2024.7.16 20:00更新：取消了所有的AC代码，改为了伪代码