搜索——深度优先搜索 DFS

深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.它的思想是从一个顶点V0开始，沿着一条路一直走到底，如果发现不能到达目标解，那就返回到上一个节点，然后从另一条路开始走到底，这种尽量往深处走的概念即是深度优先的概念。

我理解dfs和bfs依靠视频：数据结构_严蔚敏26深度_广度优先搜索

函数DFS（节点）
{
    如果（节点=目标节点） {找到目标，跳出}
    遍历所有下一层节点
    {
    DFS（下一层的节点）
    }
}

算法代码框架：

void DFS(int k)  //处理第k步
{
    if(k==n)   //已经处理到第n步,到达目的状态,输出结果
        else  //处理第k步
            for (int i=1; i<=m; i++) //第k步中有m种可能
            {
                //处理第k步
                DFS(k+1)；//进入第k+1步
            }
}

例1：从1-m个数中取n个数全排列，其中n个可以重复。

#include<iostream>
using namespace std;
const int MAX=40;
int n,m,a[MAX];
int DFS(int cur)
{
    if(cur==n)
    {
        for(int i=0; i<n; i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int i=1; i<=m; i++)
        {
            a[cur]=i;
            DFS(cur+1);
        }
    }
}
int main()
{
    cin>>m>>n;
    DFS(0);
    return 0;
}

例2：上面中n个不能重复

#include<iostream>
using namespace std;
const int MAX=40;
int n,m,a[MAX],visit[MAX];
int DFS(int cur)
{
    if(cur==n)
    {
        for(int i=0; i<n; i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int i=1; i<=m; i++)
            if(!visit[i])
            {
                a[cur]=i;
                visit[i]=1;//确定该数是否已经被访问，访问后设为1
                DFS(cur+1);
                visit[i]=0;//记得还原，因为在下一次调用的时候它未被访问
            }
    }
}
int main()
{
    cin>>m>>n;
    DFS(0);
    return 0;
}

例3：在上题的条件中加且n个数必须是从小到大。

#include<iostream>
#include<cstring>
using namespace std;
const int MAX=40;
int n,m,a[MAX];
int DFS(int cur)
{
    if(cur==n+1)
    {
        for(int i=1; i<=n; i++)
            cout<<a[i]<<" ";
        cout<<endl;
    }
    else
    {
        for(int i=a[cur-1]+1; i<=m-n+cur; i++) //起始的a[cur-1]+1原因显而易见，至于m-n+cur，因为规定了从小到大，所以i最多到这个数，打个比方：若是  m=5,n=3，那么第一个数不可能是4,5，这样个数不可能有3个，只是节省时间，可以直接<=m，对于m很小时。
        {
            a[cur]=i;
            DFS(cur+1);
        }
    }
}
int main()
{
    cin>>m>>n;
    DFS(1);//从1开始的原因是数组a的原因,从DFS中可以看出a[cur-1]，不从0开始得知
    return 0;
}