#创作计划#深度优先搜索精讲
2025-08-12 18:14:02
发布于：浙江
前言：
谢谢AC君的支持
本帖也放在了讲解题目的题解区中，欢迎各位（剩下看彩蛋）
问：
为什么我（自问自答）的精华帖都加上了自己手搓的图片
答：
因为之前一个帖子没加图片被某人喷是AI，说了也不听，后来只能删帖了（是谁我不说，不是那个素数的）。
废话不多说，正片开始。
深搜的定义：
深度优先搜索就是在一个图（树）中遍历搜索的算法，从一个根节点（如果是图的话随便找个点当根节点或按题目要求）进行深度遍历。深搜会沿着一条路径不断的深入去搜索，直到该点没有任何相邻节点或相邻节点全被探索过，即无路可走。那么这时我们就回到上一个访问的节点，继续探索该节点的路径，若该节点也没有可遍历的点则回到上一个节点继续搜索，以此类推。
深搜过程：
接下来用一个树来模拟整个深搜的过程。这里为了方便区分，空白代表未搜索，淡紫色代表已搜索，橙色代表当前搜索节点，绿色代表候选节点。且在遇到多个节点的时候左侧节点优先。作者梅鼠从没及格过，有亿点点抽象是十分正常的，望见谅。
首先我们从根节点 开始搜索，根节点 的邻居节点有节点 。按照上述规则（即以左边的节点优先，往后不再提醒）,我们先搜索节点 ,同时把节点 设为已搜索 ，并将已经搜索过的节点 和正在搜索中的节点 加入dfs序列。最后将节点 的邻居设为候选:
根据深度优先搜索的规则，我们选择最新加入的候选节点 ，将节点 设为已搜索。同时将节点 的邻居节点 设为候选。将节点 加入dfs序列：
这时我们把最新加入的节点 进行搜索，将节点 设为已搜索，将节点 加入dfs序列：
此时我们可以看见节点 没有任何邻居节点，这代表到了节点 之后已经无路可走。这时我们就回到节点 。发现节点 也没有未搜索过的邻居节点，我们就再次回到前一个节点 。这时节点 有候补节点 。我们就搜索节点 并将其加入dfs序列:
我们发现此时的节点 也没有未探索过的节点，回到节点 。节点 也没有未探索过的节点，回到节点 。此时的节点 有候补节点 和 。优先选择节点 进行探索。将节点 加入dfs序列。将其未探索的邻居节点 和 作为后补:
此时先探索节点 ，将节点 加入dfs序列。同时将节点 设为已探索。将节点 未探索过的邻居节点 设为后补:
重复上述操作，将节点 加入dfs序列，将节点 设为后补；搜索节点 ，发现无路可走，回到节点 ，发现仍旧无路可走，回到节点 。这时发现还有候补节点 。将节点 探索并加入dfs序列:
此时节点 没有未探索的邻居节点了，多次回溯回到了顶点 。这时只剩下最后一个节点 了。搜索节点 ，加入dfs序列。
至此，该树的整个深度优先搜索便完成了。不难发现，每一次搜索都会选择最后加入的节点进行搜索，这与数据结构栈的特点（先进先出）十分相似。所以我们可以使用栈进行模拟。但是现在常用的实现方法是递归搭配回溯的方法，所以这里主要讲递归。
我们用一个较小的矩阵来逐步模拟代码操作。参考题目迷宫之判定。这里我们用橙色来当做深度优先搜索递归代码的搜过的路径。我们以 当做起点， 当做终点来模拟整个递归的过程。先给出dfs主题代码：
void dfs(int x,int y){
vis[x][y]=1;
if(x==n and y==m){
p=true;
return ;
}for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1 and nx<=n and ny>=1 and ny<=m and vis[nx][ny]==0 and sz[nx][ny]!=1){
dfs(nx,ny);
}
}
}
这里我们创建两个数组，一个用来储存迷宫地形，一个用来记录是否走过。
int vis[100][100],sz[100][100];
两个方向数组分别为x坐标和y坐标。这里要注意这两个数组的数据需要两两相反。比如x的前两个数据是0,-1 ，那么y数组的数据就是 -1,0。
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
//这里分别为向下，向左，向上，向右
先分析下代码：
首先我们dfs搜索一个我们就将其设为已走过。如果x和y到达了终点我们就直接return。接下来一个for循环描绘四个走法，只要满足条件“不越界，未走过，不是墙”，我们就在该点进行dfs递归。当遇到某个点无路可走时，我们就回到前边的点。这里需要注意，前一个点的for循环还没有结束。此时就会搜索新的路径。如果依旧无路可走则再回到上一个点……直到到达终点或dfs结束，判定为无路可走。
接下来把矩阵带入代码运行：
起始点在 ， 首先将 设为已探索，而 根据for循环，首先是向下走，运气很好，满足条件，移动到 ，递归dfs函数。
记录当前节点 为已探索，按照for循环向下，满足条件，移动到 ，递归dfs：
接下来将该节点标记为已走过，然后for循环搜索，向下越界，不满足条件，向左，向右，向上，均不满足条件，这是无路可走，我们回溯到前一格 ，因为这时这里的for循环只循环了一次，且这里并没有记录 已经走过，所以不需要额外删除：
然后按照for，向左，向上均不满足条件，所以只能向右，这里的for循环结束了。我们递归dfs到 ：
记录 为已走过，然后for循环到第四次（向右），满足条件，递归dfs到 ：
记录该位置为已走过，之后在第一次for（向下）循环满足条件，向下到达 ，到达终点，改递归分支结束，将p改为true。但是注意一点，这里的深度优先搜索函数的递归并没有结束，他会尝试所有路径，但是并不会对结果产生什么影响，所以我们不需要特殊处理。如果非要处理的话可以加上
if(p)return ;
在dfs代码最开头。之后就是朴实无华的输出。完整代码：
#include <bits/stdc++.h>
using namespace std;
int sz[100][100];
int dy[4]={1,0,-1,0};
int dx[4]={0,1,0,-1};
int vis[100][100];
int n,m;
bool p=false;
void dfs(int x,int y){
vis[x][y]=1;
if(x==n and y==m){
p=true;
return ;
}for(int i=0;i<4;i++){
int nx=x+dx[i];
int ny=y+dy[i];
if(nx>=1 and nx<=n and ny>=1 and ny<=m and vis[nx][ny]==0 and sz[nx][ny]!=1){
dfs(nx,ny);
}
}
}
int main(){
cin >> n >> m;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>> sz[i][j];
}
}dfs(1,1);
cout << (p?"YES":"NO");
return 0;
}
有帮助，赞一个