#创作计划 搜索（普通、图上、树上）1
2026-07-13 15:10:32
发布于：北京
本文阅读事项：
-
建议浅色阅读，效果更好。
-
本文适合通过 4~5 级，准备学习 6~7 级内容，从算法入门过渡到算法中阶的或接触过基础算法的朋友阅读。
-
为了让各位思路更清晰，这篇帖子只讲普通 。本系列计划分为 4 篇帖子讲解，分别为：普通深搜、普通广搜、树上搜索、图上搜索。
搜索
搜索，就是找一个东西，这个东西可以是抽象化的，也可以是具象的。它对状态空间进行枚举，通过穷尽所有的可能来找到最优解，或者统计合法解的个数。想象一下，你是一只的老鼠，前面有一个洞穴，每个点都会有一些分叉，而只有一个地方放着粮食。你应该如何寻找这堆粮食呢？
基础搜索
深度优先搜索 之思路
你是一只普通老鼠。最容易想到的策略是任意选择一条路，一直往前走，直到走不通了就退回来，再重新选择一条路。不断重复这个过程，就能找到粮食了。
这样“不撞南墙不回头“的思想，就是深度优先搜索（Depth-First Search,DFS）。对于深度优先搜索，官方的解释是：
为了求解，先寻找一种可能的方向搜索，遇到障碍就回溯，直到找到解或证明无解。
这段话比较抽象，直白来讲，就是一直朝着一个方向探索，没有路了就往回退，直到把所有可能都探索完。如下图，这就是 的基础搜索过程。
接下来讲解代码实现，各位可以先不往下翻，自己想想。
深度优先搜索 之代码实现
深度优先搜索，肯定是往深入探索。那么，你一定会想到一个算法——递归！
没错，深搜可以用递归实现，也可以用栈实现。如果想了解栈的实现思路，可以自行查阅，这里讲解递归实现。但栈和递归本质上同宗同源，只不过一个用的系统栈，一个用的 STL 或数组栈而已。
递归的核心是枚举所有方向并深入搜索。但如果不加限制，可能会陷入死循环或重复计算。因此， 引入标记数组 vis[] 来记录节点状态：
-
剪枝：在进入节点前，若
vis[u]为真，说明该节点在当前路径中已访问过（或全局已处理），直接跳过，避免重复搜索。 -
回溯：对于需要枚举所有可行解的问题，在递归返回后，必须撤销当前节点的标记，以便该节点能出现在其他分支的路径中。这一点不理解没关系，待会的例题会讲到。
所以，基础的 大致有两种类型的题目：
-
迷宫问题（一维、二维），这类题目很明显是让你去搜索，比如迷宫寻路、救人等场景。
-
枚举可行解问题，要你枚举所有符合要求的解，没有明显的“搜索”之类的字眼，比如数字全排列。
我们来看一道例题：洛谷 P1706 全排列问题。
按照字典序输出自然数 到 所有不重复的排列，即 的全排列，要求所产生的任一数字序列中不允许出现重复的数字。输出时每个数字保留 个场宽。
我们以 为例。可以想象有三个空，让你用 这三个数去填。首先，第一个空 都能选，假设我们填 ,那么将 标记为已选，不能再选。
第二个空只能选 了，填 ，那么 被标记为已选，不能再选。
第三个空只能填 。
但是，这并不是唯一的填法。注意到，第二个空还可以填 ，这就需要回溯。这里要特别注意，因为之前 和 被标记为已访问了，所以退回到第二个空时，需要撤销 和 的已访问状态，这样它们才能在其他分支中被再次选择。
那么，后面的也是如此，就不一一演示了。最终，搜索出 种方案：
输出即可。
代码如下（C++）：
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n;
int vis[10], now_seq[10];
//vis[] 标记访问状态：vis[i] = 1就是访问过 now_seq[] 当前的全排列序列
//注意！k枚举的是当前的空的位置，而u枚举的是这里能填什么，有几种可能，虽然都是1~n，但是意义不同！
void dfs(int k){ //k:当前填到哪里了，哪那个空
if (k == n + 1){ //填完了
for (int i = 1; i <= n; i++){ //输出这一组全排列
cout << " " << now_seq[i]; //保留场宽输出
}
cout << endl;
return ; //直接返回
}
for (int u = 1; u <= n; u++){ //当前这一个空可以填1~n
if (vis[u]) continue ; //不能填
now_seq[k] = u; //再强调：k是位置，u是数，所以这里now_seq数组第k个位置填上u
vis[u] = 1; //这个数用了
dfs(k + 1); //填完了，继续递归，填下一个位置
vis[u] = 0; //回溯
}
}
signed main(){
cin >> n;
dfs(1); //从第一个空开始填，填到第n个空
return 0;
}
不难发现，这种题是枚举可行解问题，这类题目还有P2105 K皇后，P1219 [USACO1.5] 八皇后 Checker Challenge，B3622 枚举子集（递归实现指数型枚举）等等。
那么，这类题的模版可以归类为（C++ 伪代码）：
if (完了){
输出、计数
return ;/return 答案;
}
for (可能的情况){
if (vis[] || 边界) continue ;
计算
vis[] = 1;
dfs(下一层);
vis[] = 0;
}
return 答案;（可以不要）
接下来，我们看另一个例题：洛谷 B3625 迷宫寻路。
从 出发，只能上下左右移动，. 为空地，#是障碍，是否可以到 。能到输出 Yes，否则输出 No。。
这道题是一个典型的迷宫连通性问题。由于只需要判断“是否可达”，而不需要求出最短路径或具体路径，因此我们不需要回溯（即不需要在递归返回时取消标记）。一个格子一旦走过，就不需要再走第二次，因为再次走到该点并不会带来新的信息。
我们可以引入 dx[],dy[] 数组，他们表示下一步（上下左右）的 坐标偏移了多少，也叫做偏移量。不难发现，当前位置 上下左右的坐标如下图：
这几个位置的偏移量如下图：
所以，dx[]的值可以为 {0,0,-1,1}，dy[]的值为 {-1,1,0,0}。注意，偏移量数组作用是帮助我们快捷的计算出下一步的下标，所以，dx[i] 一定要和 dy[i] 一一对应，否则就会计算错误。注意，偏移量数组不唯一，只需要一一对应即可。
比如，i = 1时，dx[1]=-1,dy[1]=0，对应向左。只需要将原下标加上偏移量即可，即
其中， 表示方向值， 为当前坐标， 为新坐标（）。
一些细节会在代码里讲：代码如下（C++）：
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int vis[105][105]; //标记数组，1表示来过
char mp[105][105]; //地图信息
int dx[] = {0, 0, -1, 1}; //偏移量数组
int dy[] = {-1, 1, 0, 0};
// 一一对应 上 下 左 右
void dfs(int x, int y){ //x,y表示坐标
if (x == n && y == m){ //到了
return ; //返回
}
for (int i = 0; i < 4; i++){ //遍历所有方向
int nx = x + dx[i]; //新坐标
int ny = y + dy[i];
if (nx < 1 || nx > n || ny < 1 || ny > m || //越界
vis[nx][ny] || //来过
mp[nx][ny] == '#' //是障碍
) continue ; //暂停
vis[nx][ny] = 1; //标记
dfs(nx, ny); //继续递归
}
}
signed main(){
cin >> n >> m;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= m; j++){
cin >> mp[i][j];
}
}
vis[1][1] = 1; //起点标记
dfs(1, 1); //从x=1,y=1开始，到x=n,y=m结束
if (vis[n][m]) //来过(n,m)
cout << "Yes" << endl;
else cout << "No" << endl; //遍历完了都没来，说明来不了
return 0;
}
同样的题目有：P1135 奇怪的电梯，P6566 [NOI Online #3 入门组] 观星，P1141 01迷宫等等。
那么，基础 就全部讲完了，希望 @AC君 加精，各位点赞。
小彩蛋： = 电风扇 = 巅峰赛 = 等方式 = 的方式 = 大丰收 = 对方说。你打“dfs”的第一个词是什么？（我是大丰收）
有帮助，赞一个