BFS

标准BFS

原理

通过队列每次将邻接点加入，多层扩展，BFS可以求得边权为1的情况下的最短路径，因为当第一次搜索到的都是，就是最短路径。BFS要注意元素不要在出队的时候判重，要在入队之前设置为已经遍历。

模板

int dx[] = {0, -1, 0, 1}, dy[] = {1, 0, -1, 0};
int dis = 0;

while (q.size())
{
    int len = q.size();
    for (int i = 0; i < len; i ++ )
    {
        auto t = q.front();
        int x = t.first, y = t.second;
        q.pop();
        //如果是这里标记，队列里面有大量相同元素，虽然不影响最终得到正确结果，但是效率很低
        //A[x][y] = -1;
        for (int i = 0; i < 4; i ++ )
        {
            int a = x + dx[i], b = y + dy[i];
            if (a < 0 || a >= A.size() || b < 0 || b >= A[0].size()) continue;
            if (A[a][b] == -1) continue;
            if (A[a][b] == 1) return dis;
            //就是这里要在入队之前将当前入队元素标记为已经遍历
            A[a][b] = -1;
            q.push({a, b});
        }
    }
    dis ++ ;
}

多源BFS

原理

通过设置超级源点，可以将多个分散的源点合并为一个，可以解决一个点到另外多个点的最短距离问题。我们从超级源点开始做单源BFS，发现原先的多个源点只不过是BFS的第二层而已，所以多源BFS没有改变BFS的本质，不会影响结果的正确性。

例题

LC.1162 地图分析（中等）

双端队列BFS

原理

双端队列BFS可以解决图中权重仅为0和1时的情况，相当于简化的dijkstra算法，可以更快的（时间复杂度为O(m))搜到想要的答案。使用一个双端队列，队列头插入搜索权重为0的节点，队列尾插入权重为1的节点，每次从队头扩展，可以尽早的扩展那些权重为0的边，相比于BFS更快的搜索到答案。

模板

#include <deque>

void bfs()
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);

    deque<int> q;
    q.push_back(1);

    while(q.size())
    {
        int t = q.front();
        q.pop_front();

        if (st[t]) continue;
        st[t] = true;

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                if (!w[i]) q.push_front(j);
                else q.push_back(j);
            }
        }
    }
}

例题

AW.175 电路维修（简单）

AW.340 通信线路（中等）

这题是二分+双端广搜