广度优先搜索 BFS 学习笔记

广搜是图论中的基础算法之一，属于一种盲目搜寻方法。

广搜需要使用队列来实现，分以下几步：

1. 将起点插入队尾；
2. 取队首 \(u\)，如果 $u\to v $ 有一条路径，则将 \(v\) 插入队尾；
3. 如果队列不为空，重复执行 \(2\sim 3\) 步。

如上图，就是一次 BFS 的搜索过程。利用 BFS，我们可以在 \(O(n+m)\) 的时间内对一张图实现遍历，其中 \(n\) 为点数，\(m\) 为边数。

代码实现：

void bfs(int s) {
    q.push(s);
    d[s] = 0;
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = hd[u]; i; i = nxt[i]) {
            int v = to[i];
            d[v] = d[u] + 1;
            q.push(v);
        }
    }
}

其中，\(\text{hd, nxt, to}\) 均为邻接表中的数组。如果你不会什么是邻接表，那么建议先学习图论基本知识后再来看本篇文章。

应用

在 BFS 的过程中，我们求出一个 \(d\) 数组，\(d_i\) 表示起点到 \(i\) 的最短路径，也称为 \(i\) 的层级。我们发现，在 BFS 的过程中，相当于是一层一层的向外扩展。这就会带来一个很好的性质：当 \(v\) 被第一次访问，\(v\) 的最短路径就已经确定。也就是说，之后的搜索不可能搜到一个比之前更短的路径了。

BFS 过程中，队列具有单调性。也就是说，队列呈现这个样子：

给出 \(n\times n \;(n\le1000)\) 的 0-1 矩阵，\(1\) 表示不能通过，\(0\) 表示可以通过，问起点 \((sx,sy)\) 到终点 \((ex,ey)\) 至少需要走多少步。

BFS 模板题。从 \((sx,sy)\) 开始 BFS，第一次搜寻到 \((ex,ey)\) 的时候就必定是 \((sx,sy) \to (ex,sy)\) 的最短路。给出代码。注意，这里有一个小 trick，可以使用定义两个偏移量数组 \(\text{dx, dy}\) 来寻找从 \((x,y)\) 能推到的地方，详情看代码。

const int MAXN = 1005;

int n, sx, sy, ex, ey, a[MAXN][MAXN];
int dx[] = { 1, 0, -1, 0 };
int dy[] = { 0, 1, 0, -1 };
bool vis[MAXN][MAXN];

struct NODE {
    int x, y, t;
};

queue<NODE> q;

void bfs() {
    q.push((NODE){ sx, sy, 0 });
    while (q.empty() == false) {
        NODE p = q.front();
        if (p.x == ex && p.y == ey) {
            cout << p.t;
            return;
        }
        for (int i = 0; i < 4; ++i) {
            int tx = p.x + dx[i], ty = p.y + dy[i];
            if (a[tx][ty] == 0 && vis[tx][ty] == false) {
                q.push((NODE){ tx, ty, p.t + 1 });
                vis[tx][ty] = true;
            }
        }
        q.pop();
    }
}

int main(void) {
    memset(vis, true, sizeof vis);
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            char ch;
            cin >> ch;
            a[i][j] = (ch - '0' ? 1 : 0);
            vis[i][j] = false;
        }
    }
    cin >> sx >> sy >> ex >> ey;
    bfs();
    return 0;
}

这种问题称作 Flood-Fill，是 BFS 最基本的应用。

给定一个 \(n\times n\;(2\le n\le 1000)\) 的网格状地图，每个方格 \((i,j)\) 有一个高度 \(w_{i,j}\;(0\le w_{i,j} \le 10^9)\)。如果两个方格有公共顶点，则它们是相邻的。

定义山峰山谷如下：均由地图上的一个联通块组成。所有方格高度都相同。周围的方格（即不属于山峰或山谷但与山峰或山谷相邻的格子）高度均大于山谷的高度，或小于山峰的高度。

求地图内山峰和山谷的数量。特别的，如果整个地图方格的高度均相同，则整个地图即是一个山谷，也是一个山峰。

考虑 BFS。对于每个点，若未被访问，则从这个点开始 BFS。

对于每一个通过 \(u\) 搜索到的点 \(v\)，若 \(v\) 的权值与 \(w\) 的权值相同，那么就将 \(v\) 插入队尾。否则，判断如果 \(v\) 比 \(u\) 小，那么当前这个连通块只可能是山峰，否则只可能是山谷。若搜索到的这个连通块既有比他高的、也有比他矮的，那么他啥也不是。搜索后统计即可。

代码：

const int way[8][2] = {
    { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 }, { -1, -1 }, { -1, 1 }, { 1, -1 }, { 1, 1 }
};
int n, a[1010][1010], v[1010][1010], q[1000100][2], h, t, maxn, minn, ans_max, ans_min;

bool check(int x, int y) { return (x > 0 && x <= n && y > 0 && y <= n); }

void BFS(int x, int y) {
    maxn = minn = h = t = 0;
    q[++t][0] = x, q[t][1] = y;
    while (h++ < t) {
        for (int i = 0; i < 8; i++) {
            int xx = q[h][0] + way[i][0];
            int yy = q[h][1] + way[i][1];
            if (check(xx, yy)) {
                if (a[xx][yy] == a[x][y]) {
                    if (!v[xx][yy]) {
                        v[xx][yy] = 1;
                        q[++t][0] = xx, q[t][1] = yy;
                    }
                } else {
                    if (a[xx][yy] > a[x][y])
                        maxn++;  //统计周围高的
                    if (a[xx][yy] < a[x][y])
                        minn++;  //统计周围矮的
                }
            }
        }
    }
    if (!minn)
        ans_min++;  //周围没有矮的就是山峰
    if (!maxn)
        ans_max++;  //周围没有高的就是山谷
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (!v[i][j])
                BFS(i, j);
    printf("%d %d", ans_max, ans_min);
}

给出一张图，其中每条边的权值 \(w\in \{0,1\}\)，求起点 \(s\) 到终点 \(e\) 的最短路。要求 \(O(n)\) 求解。

这道题目是一道非常巧妙的题目。我们要是使用原本的 BFS 搜索，就有可能不满足要求的队列单调性。如当搜索以下图的时候，\(5\) 节点由于层级比 \(2\) 深，于是会在 \(2\) 之后入队，但是他的权值又比 \(2\) 小，所以就不满足队列的单调性了。

如何解决这个问题呢？观察到每条路的权值为 \(0\) 或 \(1\)，那么也就是说，假设目前搜索到点 \(u\)，\(u \to v\) 有一条权值为 \(w\) 的路径，那么如果 \(w=1\)，就把 \(v\) 放入队尾，否则放入队头。这样，我们仍能保证队列的单调性。读者可以模拟一下上图 BFS 的过程，感受双端队列 BFS 的巧妙之处。