A3阶段 第七课 深度优先搜索
2025年6月28日
学习时长
约1.5小时
难度
A3阶段/CSP-J
标签
数据结构
讲师
王骏峣
深度优先搜索
利用递归函数来实现暴力枚举
将问题需要决策的部分分为若干个阶段
例如想要输出所有长度为n的排列，分为n个阶段，第i个阶段决定排列的第i个位置，对于每个阶段，都可以选择1~n之间的数填入
因此，可以设计一个递归算法：从第一个位置开始，用循环枚举当前位置的值，再往下一个位置递归
代码结构
void dfs(int p){
if(p == n + 1){
判断当前a数组是否为一个阶段，若是，则输出
return;
}
for(int i = 1;i <= n;i ++){
a[p] = i;
dfs(p + 1);
}
}
主函数调用：dfs(1);
上述代码的复杂度过高，为O(nn)
注意到如果前面的序列里出现了重复的数字，那么无论后面填入什么都不可能是排列
优化思路：一旦发现再往后搜也不会得到合法解的时候，提前返回（搜索的可行性剪枝）
剪枝实现
用vis数组标记第i个数字是否被使用
代码结构
int vis[N];
void dfs(int p){
if(p == n + 1){
for(int i = 1;i <= n;i ++)
cout << a[i] << " ";
cout << endl;
return;
}
for(int i = 1;i <= n;i ++){
if(vis[i] == 0){
a[p] = i;
vis[i] = 1;
dfs(p + 1);
vis[i] = 0;
}
}
}
主函数调用：dfs(1);
dfs结束后，需要枚举将下一个数字填入第p个位置，先将当前填入的数字i标记撤销，这一步称为回溯
若将状态与状态之间的联系看作树,
深度优先搜索对状态的遍历顺序和
树的深度优先遍历是一致的
这也是剪枝的名字由来,即
剪去搜索树上的一部分枝条
深度优先搜索的局限性
- 深度优先搜索本质上也是暴力枚举，时间复杂度偏高
- 只适用于数据规模较小的题目
- 或者用于取部分分