搜索——深度优先搜索 DFS

z4zr 2013-05-29 PM 2109℃ 0条

深度优先搜索属于图算法的一种,英文缩写为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;
}
标签: dfs, acm, 搜索

非特殊说明,本博所有文章均为博主原创。

评论啦~