DFS算法与实例
本文最后更新于 481 天前,其中的信息可能已经有所发展或是发生改变。

大家好,我是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原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接: https://nth.ink/cpp/P105.html

(广告由我们的赞助商提供,内容与本站无关)
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇