首页 > dfs与bfs
头像
大大大芒果
编辑于 2021-04-17 16:00
+ 关注

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) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐