DFS深度优先搜索-入门 笔记
DFS 依靠递归的思想，总是往更远的方向行进，直到达到边界，再返回到上一步考虑另外的方向
（递归-回溯）
从 \(1\)~\(n\) 这 \(n\) 个整数中随机选取任意多个，输出所有可能的选择方案，即计算\(2^n\)
我们考虑有 \(n\) 个空位，每次都选择填或不填数字进去
同时记录该数字的状态：选择中、填、不填 一共三种状态，所以需要一个数组来存储他们
int n;
int state[20];
然后来构造 dfs 函数：使用 x 这个变量来作为形式参数，意思是当前考虑到了第几个空位
void dfs(int x){
......
}
此时第 x 位的状态为初始化的 \(0\) ，表示在选择中，每个空位都有两种选择：填或不填
我们把填的状态记作 \(1\) ，不填的状态记作 \(2\)
state[x]=1;//选择填入
dfs(x+1);
state[x]=0;
state[x]=2;//选择不填入
dfs(x+1);
state[x]=0;
每次选择填或不填后，再次调用 dfs 递归考虑下一个空位，递归完成后，我们将这一位的状态复位，即state[x]=0（回溯）
当递归到没有空位的情况时，我们就输出方案：
if (x>n){//第x位超过了我们给定的n
for (int i=1;i<=n;i++){
if (state[i]==1)//当第i位的状态为1（选了），我们就输出该位填入的数
printf("%d ",i);
}
printf("\n");
return ;//终止递归，开启回溯
}
完整代码：
#include <stdio.h>
int n;
int state[20];
void dfs(int x){
if (x>n){
for (int i=1;i<=n;i++){
if (state[i]==1)
printf("%d ",i);
}
printf("\n");
return ;
}
state[x]=1;
dfs(x+1);
state[x]=0;
state[x]=2;
dfs(x+1);
state[x]=0;
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}
从 \(1\)~\(n\) 这 \(n\) 个整数中随机选出 \(m\) 个，输出所有可能的选择方案，即计算\(C_n^m\)
DFS要求我们的方案做到不重不漏，对应组合数的计算，采用“不回头”的策略
还是考虑第 \(x\) 位填不填数字进去，只是需要增加一个参数来记录我们从第几个数开始选数字（不回头）
填第 x 个空位时，我们从第 str 项开始
void dfs(int x, int str){
......
}
使用for循环来对 n 个数依次进行考虑，定义arr 数组，存储我们的方案
for (int i=str;i<=n;i++){
arr[x]=i;
dfs(x+1,i+1);
arr[x]=0;
}
从 \(1\) 开始考虑，每次填入 arr 数组的第 x 位，然后递归到第 x+1 位，并从第 i+1 项开始选择
最后递归到 x>n 时结束递归，输出arr 数组中每一位填入的数
if (x>m){
for (int i=1;i<=m;i++){
printf("%d ",arr[i]);
}
printf("\n");
return;
}
完整代码：
#include <stdio.h>
int n,m;
int arr[52];
void dfs(int x, int str){
if (x>m){
for (int i=1;i<=m;i++){
printf("%d ",arr[i]);
}
printf("\n");
return;
}
for (int i=str;i<=n;i++){
arr[x]=i;
dfs(x+1,i+1);
arr[x]=0;
}
}
int main()
{
scanf("%d %d",&n,&m);
dfs(1,1);
return 0;
}
把 \(1\)~\(n\) 这 \(n\) 个整数排成一行后随机打乱顺序，输出所有可能的次序，即计算\(A_n^n\)
我们一样考虑第 \(x\) 位填入数字的操作，但是每次填入的数字都可以取未填过的，因为需要考虑排列顺序
void dfs(int x){
......
}
我们开一个bool数组来记录数字的状态（选过了，未选过）
使用for 循环来遍历所有数字的状态，选择未被使用过的数字填入第 x 位
for (int i=1;i<=n;i++){
if (!st[i]){//选择未被使用过的数
arr[x]=i;
st[i]=1;//标记该数已被使用
dfs(x+1);
st[i]=0;//回溯
}
}
当 x>n 即填完了所有空位后，结束递归，输出arr数组记录的填入的数字
if (x>n){
for (int i=1;i<=n;i++){
printf("%d ",arr[i]);
}
printf("\n");
return;
}
完整代码：
#include <stdio.h>
int n, arr[10];
bool st[10];
void dfs(int x){
if (x>n){
for (int i=1;i<=n;i++){
printf("%d ",arr[i]);
}
printf("\n");
return;
}
for (int i=1;i<=n;i++){
if (!st[i]){
arr[x]=i;
st[i]=1;
dfs(x+1);
st[i]=0;
}
}
}
int main()
{
scanf("%d",&n);
dfs(1);
return 0;
}