DFS算法（深度优先搜索）_void dfs

1. 5种形式：

        a. 排序树：孩子不与祖先重复

        b. 组合树：孩子大于父亲

        c. 子集树：左孩子为0，右孩子为1

        d. 拆分树：孩子>=父亲

        e. 搜索树：孩子不与祖先重复

注：黄色点是返回时的标注。

2. 判答案的两种方法

a. 判孩子（当根节点是虚空的时候，比如子集树，排列树，拆分树，组合树）

#include <bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
void dfs(int k);//第k层/代/步
int ans[N];//记录答案
int vis[N];//标记变量，去重
int main()
{
    
    return 0;
}
void dfs(int k)
{
    for(int i=1; i<=N; i++)//枚举第k代的所有孩子的线索
    {
        //生成孩子（用i表示出孩子）
        if()//判孩子的合法性（符合约束条件并且不重复）
        {
            //保存孩子
            //标记孩子
            if()//如果孩子是答案就输出（判孩子法）
            {
                
            }
            else//如果孩子不是答案，继续从下一代找
            {
                
            }
            //取消标记
        }
    }
}

b. 判父亲（当根节点不是虚空的时候，比如搜索树）

#include <bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
void dfs(int u);//u为父亲结点
int ans[N];//记录答案
int vis[N];//标记变量，去重
int main()
{
 
    return 0;
}
void dfs(int u)
{
    //保存父亲
    //标记父亲
    if()//如果父亲是答案就输出（判父亲法）
    {
        //输出答案
    }
    else//如果父亲不是答案，继续从下一代找
    {
        for(int i=1; i<=N; i++)//枚举第u代的所有孩子的i
        {
            //生成孩子
            if()//判孩子合法性
            {
                dfs(i);//递归搜索u的孩子i
            }
        }
    }
    //取消标记
}

3. 代码

a. 排序树

#include<bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
void dfs(int k);//第k层/代/步
int ans[N];//记录答案
int vis[N];//标记变量，去重
 
int n;
 
int main()
{
    cin>>n;
    dfs(1);
    return 0;
}
void dfs(int k)
{
    for(int i=1; i<=n; i++)//枚举第k代的所有孩子的线索
    {
        //生成孩子（用i表示出孩子）
        if(vis[i]==0)//判孩子的合法性（符合约束条件并且不重复）
        {
            //保存孩子
            ans[k]=i;
            //标记孩子
            vis[i]=1;
            if(k>=n)//如果孩子是答案就输出（判孩子法）
            {
                for(int j=1; j<=k; j++)
                {
                    cout<<ans[j];
                }
                cout<<endl;
            }
            else//如果孩子不是答案，继续从下一代找
            {
                dfs(k+1);
            }
            //取消标记
            vis[i]=0;
        }
    }
}

b. 组合树

#include<bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
void dfs(int k);//第k层/代/步
int ans[N];//记录答案
int vis[N];//标记变量，去重
 
int n, r;//从n个数里面取r个数进行组合
 
int main()
{
    cin>>n>>r;
    dfs(1);
    return 0;
}
void dfs(int k)
{
    for(int i=1; i<=n; i++)//枚举第k代的所有孩子的线索
    {
        //生成孩子（用i表示出孩子）
        if(i>ans[k-1])//判孩子的合法性（符合约束条件并且不重复）
        {
            //保存孩子
            ans[k]=i;
            //标记孩子
            if(k>=r)//如果孩子是答案就输出（判孩子法）
            {
                for(int j=1; j<=k; j++)
                {
                    cout<<ans[j];
                }
                cout<<endl;
            }
            else//如果孩子不是答案，继续从下一代找
            {
                dfs(k+1);
            }
            //取消标记
        }
    }
}

c. 子集树

#include <bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
void dfs(int k);//第k层/代/步
int ans[N];//记录答案
int main()
{
    dfs(1);//从第一步开始
    return 0;
}
void dfs(int k)
{
    for(int i=0; i<=1; i++)//枚举第k代的所有孩子的线索
    {
        //生成孩子（用i表示出孩子）
        if(1)//判孩子的合法性（符合约束条件并且不重复）
        {
            //保存孩子
            ans[k]=i;
            //标记孩子
            if(k>=4)//如果孩子是答案就输出（判孩子法）
            {
                for(int j=1; j<=k; j++)
                {
                    cout<<ans[j];
                }
                cout<<endl;
            }
            else//如果孩子不是答案，继续从下一代找
            {
                dfs(k+1);
            }
            //取消标记
        }
    }
}
/*
输出：0表示不选，1表示选择
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
*/

d. 拆分树

#include <bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
void dfs(int n, int k);//第k层/代/步
int ans[N];//记录答案
int main()
{
    ans[0]=1;//初始化时，一定要将ans[0]设成1，因为所有的孩子都必须>=1
    dfs(5, 1);
    return 0;
}
void dfs(int n, int k)
{
    for(int i=1; i<=n; i++)//枚举第k代的所有孩子的线索
    {
        //生成孩子（用i表示出孩子）
        if(i>=ans[k-1])//判孩子的合法性（符合约束条件并且不重复）
        {
            //保存孩子
            ans[k]=i;
            //标记孩子
            n-=i;
            if(n==0)//如果孩子是答案就输出（判孩子法）
            {
                for(int j=1; j<=k; j++)
                {
                    cout<<ans[j]<<" ";
                }
                cout<<endl;
            }
            else//如果孩子不是答案，继续从下一代找
            {
                dfs(n,k+1);
            }
            //取消标记
            n+=i;
        }
    }
}

e. 搜索树（找起点到终点的所有路径）

#include <bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
 
int n,m;//n点，m边
vector<int> a[N];//动态数组存储图
 
void dfs(int u, int k);//u为父亲结点,第k步
int ans[N];//记录答案
int vis[N];//标记变量，去重
 
//找到从起点到终点的所有路径
int start=0, target=2;
int main()
{
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int u, v;
        cin>>u>>v;
        a[u].push_back(v);
        a[v].push_back(u);
    }
    dfs(start,1);
    return 0;
}
void dfs(int u, int k)
{
    //保存父亲
    ans[k]=u;
    //标记父亲
    vis[u]=1;
    if(u==target)//如果父亲是答案就输出（判父亲法）
    {
        //输出答案
        for(int i=1; i<=k; i++)
        {
            cout<<ans[i]<<" ";
        }
        cout<<endl;
    }
    else//如果父亲不是答案，继续从下一代找
    {
        for(int i=0; i<a[u].size(); i++)//枚举第u代的所有孩子的i
        {
            int v=a[u][i];//u的第i个孩子
            if(vis[v]==0)
            {
                dfs(v,k+1);//递归搜索u的孩子i
            }
        }
 
    }
    //取消标记
    vis[u]=0;
}
/*
5 7
0 1
0 3
0 4
1 2
1 4
2 3
3 4
*/

4. 实例

1317组合树

1318拆分树

1212搜索树

#include <bits/stdc++.h>
using namespace std;
#define N 25//问题的规模
void dfs(int ii, int jj, int k);//u为父亲结点
int vis[N][N];//标记变量，去重
 
char a[N][N];
int number[26];
int maxl=0;
int r,s;
int di[4]= {-1,1,0,0};
int dj[4]= {0,0,-1,1};
 
int main()
{
    cin>>r>>s;
    for(int i=0; i<r; i++)
    {
        for(int j=0; j<s; j++)
        {
            cin>>a[i][j];
        }
    }
    dfs(0,0,1);
    cout<<maxl;
    return 0;
}
void dfs(int ii,int jj,int k)
{
    //保存父亲
    //标记父亲
    vis[ii][jj]=1;
    number[a[ii][jj]-'A']=1;
    if(k>maxl)//如果父亲是答案就输出（判父亲法）
    {
        //输出答案
        maxl=k;
    }
    for(int i=0; i<4; i++)//枚举第u代的所有孩子的i
    {
        //生成孩子
        int ni=ii+di[i];
        int nj=jj+dj[i];
        if(ni>=0 && ni<r && nj>=0 && nj<s && vis[ni][nj]==0 && number[a[ni][nj]-'A']==0)//判孩子合法性
        {
            dfs(ni, nj, k+1);//递归搜索u的孩子i
        }
    }
    //取消标记
    vis[ii][jj]=0;
    number[a[ii][jj]-'A']=0;
}

1213排列树

#include<bits/stdc++.h>
using namespace std;
#define N 1000//问题的规模
void dfs(int k);//第k层/代/步
int ans[N];//记录答案
int vis[N];//标记变量，去重
 
int n;
int cnt;
int check(int k, int i);
 
int main()
{
    n=8;
    dfs(1);
    return 0;
}
void dfs(int k)
{
    for(int i=1; i<=n; i++)//枚举第k代的所有孩子的线索
    {
        //生成孩子（用i表示出孩子）
        if(vis[i]==0 && check(k,i)==1)//判孩子的合法性（符合约束条件并且不重复）
        {
            //保存孩子
            ans[k]=i;
            //标记孩子
            vis[i]=1;
            if(k>=n)//如果孩子是答案就输出（判孩子法）
            {
                cnt++;
                cout<<"No. "<<cnt<<endl;
                for(int j=1; j<=k; j++)
                {
                    for(int p=1; p<=k; p++)
                    {
                        if(p==ans[j])
                        {
                            cout<<1<<" ";
                        }
                        else
                        {
                            cout<<0<<" ";
                        }
                    }
                    cout<<endl;
                }
            }
            else//如果孩子不是答案，继续从下一代找
            {
                dfs(k+1);
            }
            //取消标记
            vis[i]=0;
        }
    }
}
int check(int k, int i)
{
    for(int j=1; j<k; j++)
    {
        if(ans[j]==i)
        {
            return 0;//在同一列返回0
        }
    }
    for(int j=1; j<k; j++)
    {
        if(k-j==ans[j]-i || k-j==i-ans[j])
        {
            return 0;//在同对角线上返回0
        }
    }
    return 1;
}