DFS算法与实例

大家好,我是ZiXiang,Wei,现在,我来向大家介绍通过递归算法来实现深度优先搜索。

深搜,英语名是depth first search,是尽可能深的搜索一棵树的项,就像这样:

深搜属于盲目搜索,最糟糕的情况为时间复杂度为O(!n)。

基本结构:

int check(参数)
{
    if(满足条件)
        return 1;
    return 0;
}

void dfs(int step)
{
        判断边界
        {
            相应操作
        }
        尝试每一种可能
        {
               满足check条件
               标记
               继续下一步dfs(step+1)
               恢复初始状态(回溯的时候要用到)
        }
}   

到底什么是DFS,如何用它解决实例,下面用一个实例:

//全排列问题
#include<stdio.h>
#include<string.h>

int n;
char  a[15];
char re[15];
int vis[15];
//假设有n个字符要排列,把他们依次放到n个箱子中
//先要检查箱子是否为空,手中还有什么字符,把他们放进并标记。
//放完一次要恢复初始状态,当到n+1个箱子时,一次排列已经结束
void dfs(int step)
{
    int i;
    if(step==n+1)//判断边界
    {
        for(i=1;i<=n;i++)
            printf("%c",re[i]);
        printf("\n");
        return ;
    }
    for(i=1;i<=n;i++)//遍历每一种情况
    {
        if(vis[i]==0)//check满足
        {
            re[step]=a[i];
            vis[i]=1;//标记
            dfs(step+1);//继续搜索
            vis[i]=0;//恢复初始状态
        }
    }
    return ;
}

int main(void)
{
    int T;
    scanf("%d",&T);
    getchar();
    while(T--)
    {
        memset(a,0,sizeof(a));
        memset(vis,0,sizeof(vis));//对存数据的数组分别初始化
        printf("%s",a+1);
        n=strlen(a+1);
        dfs(1);//从第一个箱子开始
    }
    return 0;
}

总结一下:DFS用四个字概括:勇往直前,DFS搜索树没搜索到叶子节点就不会回溯,搜索到叶子节点后,用递归继续。

PS这是萌新的第一个文章,有bug请见谅。

Alex172

  蔡徐坤打篮球是怎么回事呢?蔡徐坤相信大家都很熟悉,但是蔡徐坤打篮球是怎么回事呢,下面就让小编带大家一起了解吧。   蔡徐坤打篮球,其实就是蔡徐坤打篮球,大家可能会很惊讶蔡徐坤怎么会打篮球呢?但事实就是这样,小编也感到非常惊讶。   这就是关于蔡徐坤打篮球的事情了,大家有什么想法呢,欢迎在评论区告诉小编一起讨论哦!

相关推荐

Leave a Reply

Your email address will not be published. Required fields are marked *

微信扫一扫

微信扫一扫

微信扫一扫,分享到朋友圈

DFS算法与实例
返回顶部

显示

忘记密码?

显示

显示

获取验证码

Close