#创作计划#浅谈双源BFS doge=)

复仇者_ドラゴンコア

2024-11-21 15:03:18

发布于：浙江

24阅读

0回复

0点赞

上一期啊，讲了BFS,（~~虽然更多人看到的是暑假小逝~~）那么在上一期结尾，我说过有个叫双源BFS的东西，十分的牛b吽吽，那今天就来浅讲一手§(￣▽￣)§

1.0 基本思想

要知道，双源这名字一听就高大上，那怎么区分这玩意和普通BFS的区别呢？，那本狗就不得不讲一个例子了.....

一只舔狗，舔他的女神，年年舔，月月舔，日日舔，可能舔三年才能感动女神..._{不排除女神拒绝了，爆了个MLE，嘻嘻φ(゜▽゜*)♪} 所以这就是典型的单相思（BFS）_{没结果的！}你看隔壁，小帅和小美本来就那啥，表个白恐怕三分钟就够了...._{单身狗小声哭泣ing(ノへ￣、)}
这就是双源BFS。

咳咳（战术清嗓），扯远了。从刚刚那个生动形象的例子就可以知道，双源BFS的基本思想就是双向奔赴，而且也可以看到他很明显的优势就是快！（效率高），而且他还有一个优势就是省内存（毕竟可以更快相遇）

1.5 适用范围

双源BFS的应用范围还算广，毕竟能够应对的数据范围更大，主要还是分3类：
1. 一般搜索问题（略）
2. 搜索问题butBFS或DFS不顶事er
3. 题有明确的特征（强制把一坨双源BFS塞你嘴里）

2.0 具体实现

双源BFS有两种实现方法，主要差别在需要维护的队列数量上.....

即顺序和逆序共用队列和不共用队列

2-A 共用队列
这种情况每次出入队都得两个两个来，如下：

queue<node> a;//共用队列
a.push(A);//起始点
a.push(B);//终点
while(a.size())
{
    node nowa=a.front()//顺序BFS
    a.pop();//记得出队
    node nowb=a.front()//再来一遍！but逆序    
    a.pop();
}

还有一个注意点！怎么停止循环？
只要两个点相同就好了啦！^o^/
如下：

if(nowa==nowb)
{
    return;    
}

除了以上代码外，其他基本代码大体相同，不予给出_{其实是我懒得敲━━(￣ー￣*|||━━}。
2-B 不共用队列
其实出入队也差不多，长这样：

queue<node> a;
queue<node> b;
a.push(A);//起始点
b.push(B);//终点
while(a.size())
{
    node nowa=a.front()//顺序BFS
    a.pop();//记得出队
    node nowb=b.front()//再来一遍！but逆序    
    b.pop();
}

这里再把停止给出~ _{其实两个一样，所以空一行给个空气U•ェ•*U}

我是空气我是空气我是空气我是空气我是空气我是空气我是空气

然后是扩展邻居，两个差不多所以一起给 ~~懒 _〆(´Д｀）~~

for(int i=0;i<4;i++)//经典四方向
{
    int anx=nowa.x+dx[i];
    int any=nowa.y+dy[i];
    int bnx=nowb.x+dx[i];
    int bny=nowb.y+dy[i];
    if(我是条件)
   ｛
        a.push({anx,any});
        a.push({bnx,bny});
        //双队列写成这样：
        //a.push({anx,any});
        //b.push({bnx,bny});
    ｝
}