广度优先搜索 BFS 学习笔记

引入

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

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

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

广度优先搜索 BFS 学习笔记-LMLPHP

如上图,就是一次 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 学习笔记-LMLPHP

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

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

广度优先搜索 BFS 学习笔记-LMLPHP

例题1 走迷宫

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 最基本的应用。

例题2 山峰山谷

考虑 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);
}

例题3 0/1 最短路

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

广度优先搜索 BFS 学习笔记-LMLPHP

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

04-24 08:43