深度优先搜索（dfs）题目合集

全排列问题 dfs原理和模版

P1706 全排列问题 - 洛谷 | 计算机科学教育新生态

深度优先搜索原理（纯个人理解）

和循环做对比：

两层循环嵌套的情况下，假设内层循环运行到一半时我不想运行了，我想把外层循环的状态往回拨（例如for循环一般用一个进度标记变量i表示循环进度，修改i的值用以控制循环）重新开始。

但是直接终止内层循环的话，即使修改外层循环的循环进度，也无法回到外层循环之前的状态，或者说需要付出巨大的条件。

我们知道，递归是函数调用自己本身。底层有专门的寄存器记录当前函数的进度，当函数递归时，在函数所在的栈空间会生成一个和自己一样的函数先执行，新生成的函数执行完了，会回到原来的函数原来的进度继续进行。

利用这个特性，我们用递归代替外层的循环，内部再用一个循环，这样内层循环运行到一半不想运行了，直接退出当前函数，回到上一层函数发生递归的语句后，继续运行。这样做的最大好处是可以以非常低的成本回到之前的状态。

这种利用递归和栈的特性实现的枚举方式被称作**深度优先搜索（depth first search，简称dfs）**算法。

例如这题枚举全排列，假设枚举到1,2,3时，输出123，然后3的空位让出来，3后面没有数字了，回到2,2的后面还有一个3，于是有了1,3；再到第三个空位，此时有1,2可以用，1之前用过了，就把2放上去，于是就有了132。

利用这个思路，即可完成全排列的枚举。而这个思路也是dfs的通用思路。

用这个算法时一定要想清楚状态，以及回来（书上和资料上叫回溯）的时候，哪些状态要还原，哪些不还原。例如这里1之前用过了，后面就不能用了，等之前的用完了才能用。

参考程序

#include<stdio.h>int flag[10];
int ans[10],p;//深度优先搜索
void dfs(int n,int depth){if(depth>n){int i=0;for(i=1;i<=n;i++){printf("%5d",ans[i]);}printf("\n");return;}int i=1;for(i=1;i<=n;i++){if(flag[i]==1)continue;flag[i]=1;//标记状态，下层枚举时跳过这层 ans[++p]=i;//记录答案 dfs(n,depth+1);//前往下一层 --p;//回溯 flag[i]=0;//回到之前的状态}
}int main() {int n;scanf("%d",&n);dfs(n,1);return 0;
}

但这个算法的时间复杂度一般都是平方甚至是指数级，若递归太深还会导致栈溢出。所以dfs也有很大的局限性。为了降低复杂度和减少栈溢出，有很多技巧（有的大佬称之为剪枝）可以进行，后面有刷到相关的题就提一下。

dfs通用模版

模拟两层循环的dfs模版：

void dfs(int depth, 其他参数){//depth用于标记递归深度，可以没有if(depth太深不给往下走了或其他情况){整理状态;return;}if(其他情况（如果有的话，虽然可以放在一个if里处理）){整理状态;return;}//...for(初始情况;是否枚举完了所有情况;){if(情况1不符合条件)continue;if(情况2不符合条件)continue;//...标记状态;处理当前情况;dfs(depth+1，其他参数);将标记的状态回溯到原来的样子;}
}

个人更喜欢用这个，因为在比赛的环境下，自己并不能一下子想到所有不符合条件的情况或状态，所以用这个模版的话想到一个添加一个，也不用修改之前的判断。

当然，模版并不唯一，只要能理解整个思路，以及整理好实际问题的所有状态，就能用dfs解决问题。

素数环

2110：【例5.1】素数环

参考程序：

#define _CRT_SECURE_NO_WARNINGS 1/*
http://ybt.ssoier.cn:8088/problem_show.php?pid=2110
*/#include<iostream>
#include<cmath>
#define endl "\n"
using namespace std;bool flag[31] = { 0 };
int n = 0;
int ans[31] = { 0 };//数据范围不超过30，所以数组开31个空间bool prime(int x) {//判断素数if (x == 2)return true;if (x < 2)return false;int i = 2;while (i <= sqrt(x) && x % i != 0)i++;if (x % i == 0)return false;return true;
}inline int judg(int x) {//防止数据越界if (x > n)return 1;if (x < 1)return n;return x;
}void dfs(int depth) {if (depth == n+1) {//所有空位都填满了flag[0] = true;return;}for (int i = 1; i <= n; i++) {if (flag[i])//这个数字用过continue;//上一个空填有数字，并且i和那个数字的和不是素数if (ans[judg(depth - 1)] != 0 && !prime(i + ans[judg(depth - 1)]))continue;if (ans[judg(depth + 1)] != 0 && !prime(i + ans[judg(depth + 1)]))continue;ans[depth] = i;flag[i] = true;dfs(depth + 1);if (!flag[0]) {//如果凑齐了一个环，就不回溯，等所有递归解除回到main函数flag[i] = false;ans[depth] = 0;}}
}int main()
{cin >> n;dfs(1);for (int i = 1; i <= n; i++)cout << ans[i] << ' ';return 0;
}

组合的输出 剪枝+新dfs模版

1317：【例5.2】组合的输出

剪枝的一个例子。

举1为根结点的树的例子，画红圈的都是不要的结点，应该剪去。

参考程序

剪去结点的方法很多，比如在内层循环中作判断：

#include<iostream>
#include<cstdio>
using namespace std;int n, r, num[101];
bool vis1[101] = { 0 };
void dfs1(int dep)
{if (dep == r + 1){for (int i = 1; i < dep; i++)printf("%3d", num[i]);printf("\n");return;}for (int i = 1; i <= n; i++){if (!vis1[i]&&i>num[dep-1])//这层递归填进去的答案比上一层大{vis1[i] = 1;num[dep] = i;dfs1(dep + 1);vis1[i] = 0;}}
}int main()
{cin >> n >> r;dfs1(1);return 0;
}

或者对内部的循环的枚举范围进行限制：

#include<iostream>
#include<cstdio>
using namespace std;int n, r, num[101];
bool vis1[101] = { 0 };
void dfs1(int dep) {if (dep == r + 1) {for (int i = 1; i < dep; i++)printf("%3d", num[i]);printf("\n");return;}//从上一层的最大数开始枚举，很不错的剪枝 for (int i = num[dep - 1] + 1; i <= n; i++) {if (!vis1[i]) {vis1[i] = 1;num[dep] = i;dfs1(dep + 1);vis1[i] = 0;}}
}int main() {cin >> n >> r;dfs1(1);return 0;
}

可以的话尽量用第2种思路，第2种思路直接规避掉了很多不必要的判断。

新的dfs模版

void dfs(int depth, 其他参数){//depth用于标记递归深度，可以没有if(depth太深不给往下走了或其他情况){整理状态;return;}if(其他情况（如果有的话，虽然可以放在一个if里处理）){整理状态;return;}//...for(初始情况;是否枚举完了所有情况;){if(符合条件){标记状态;处理当前情况;dfs(depth+1，其他参数);将标记的状态回溯到原来的样子;}}
}

自然数的拆分 利用形参进行回溯

1318：【例5.3】自然数的拆分

例如这个样例：

7=1+1+1+1+1+1+1
7=1+1+1+1+1+2
7=1+1+1+1+3
7=1+1+1+2+2
7=1+1+1+4
7=1+1+2+3
7=1+1+5
7=1+2+2+2
7=1+2+4
7=1+3+3
7=1+6
7=2+2+3
7=2+5
7=3+4

后面输出的数都不比前面的小，又都能保证全部加起来等于7。

所以用到上题的剪枝。

参考程序：

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif
#include<iostream>
using namespace std;
int ans[101] = { 0 };
int total = 0;void dfs(int depth, int n, int sum, int ls) {if (sum == 0) {++total;cout << n << "=";for (int i = 1; i < ans[0]; i++)cout << ans[i] << "+";cout << ans[ans[0]] << endl;return;}if (depth > n || sum < 0)return;for (int i = ls; i < n; i++) {ans[++ans[0]] = i;//没有明显的条件限制dfs(depth + 1, n, sum - i, i);--ans[0];//回溯}
}int main() {int n = 0;cin >> n;dfs(1, n, n, 1);return 0;
}

发现参考程序可以进一步被优化。例如n作为全局变量，sum记录枚举的数的和，当递归到下一层时，sum+i作为实参传递给下一层，回来之后，sum还是sum。

因为sum是形参，可以理解为局部变量，局部变量出了自己的作用域就用不了了，而每层递归的形参和上层递归的关系只有上层递归传值给这层递归。利用这个原理，可以实现自动回溯。

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS 1
#endif
#include<iostream>
using namespace std;
int ans[101] = { 0 };
int total = 0;
int n = 0;void dfs(int depth, int sum) {if (sum > n)return;if (sum == n) {cout << n << "=";for (int i = 1; i < depth - 1; i++)cout << ans[i] << "+";cout << ans[depth - 1] << endl;return;}for (int i = ans[depth - 1]; i < n; i++) {ans[depth] = i;dfs(depth + 1, sum + i);}
}int main() {cin >> n;ans[0] = 1;dfs(1, 0);return 0;
}