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请见谅。

0 0 vote
Article Rating
Subscribe
提醒
0 评论
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x