dfs与bfs

1、dfs
dfs就是我们常说的深度优先搜索,它的思路就是:我们每一次搜索到一个点的时候,如果这个点不符合条件,那么就return,返回到上一层(就是常说的回朔),如果这个点符合条件,就一直搜索下去,直到没有点可以搜索。

不过要记得,走过的点一定要记录下来,不然整个递归过程就会无穷无尽。

图片说明

比如上面这张图,搜索过程就是:
从1到2,2到3,3到4,4到5,5到6,6到7,7到8,8到9,9到10,10到11

接下来是深搜代码:

void dfs(int deep)
{
    int x=deep/n,y=deep%n;
    if(符合某种要求||已经不能在搜了)
    {
        做一些操作;
        return ;
    }
    if(符合某种条件且有地方可以继续搜索的)//这里可能会有多种条件,可能要循环什么的
    {
        a[x][y]='x';//可能要改变条件,这个是瞎写的
            dfs(deep+1,sum+1);//搜索下一层
        a[x][y]='.';//可能要改回条件,有些可能不用改比如搜地图上有多少块连续的东西
    }
}

2、bfs
bfs就是我们常说的广度优先搜索或宽度优先搜索,它的思路就是:我们每一次搜索到一个点的时候,如果这个点不符合条件,那么搜索同一层中符合条件的点,再把这一层中符合要求的点一一拓展,按照上述形式搜索下去。

和dfs一样,走过的点一定要记录下来,不然整个递归过程就会无穷无尽。

用dfs的例子图,用bfs走一遍。

图片说明

搜索过程就是:
从1到2,2到5,5到7,7到3,3到4,4到6,6到8,8到9,9到10,10到11

接下来是广搜代码:

void bfs1(node p)
{
    node t,tt;
    v.push(p);
    while(!v.empty())
    {
        t=v.front();//取出最前面的
        v.pop();//删除
        if(找到符合条件的)
        {
            做记录;
            while(!v.empty()) v.pop();//如果后面还需要用,随手清空队列
            return;
        }
        visit[t.x][t.y]=1;//走过的进行标记,以免重复
        rep(i,0,4)//做多次查找
        {
            tt=t;
            tt.x+=dir[i][0];tt.y+=dir[i][1];//这里的例子是向上下左右查找的
            if(如果这个位置符合条件)
            {
                tt.bits++;//步数加一
                v.push(tt); //把它推入队列,在后面的时候就可以用了
            }
        }
    }
}

锦囊:
如果bfs过不了,就用dfs。
如果dfs过不了,就用bfs。
因为bfs和dfs会处理不同的图,时限也会不一样。

如果dfs和bfs都过不了,就......

#学习路径#
全部评论
感谢参与【创作者计划2期·技术干货场】!欢迎更多牛油来写干货,瓜分总计20000元奖励!!技术干货场活动链接:https://www.nowcoder.com/link/czz2jsghtlq(参与奖马克杯将于每周五结算,敬请期待~)
点赞 回复 分享
发布于 2021-03-26 10:51

相关推荐

04-24 14:07
东南大学 C++
点赞 评论 收藏
分享
评论
1
5
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务