廣度優先搜索 BFS 學習筆記
- 2022 年 4 月 24 日
- 筆記
廣度優先搜索 BFS 學習筆記
引入
廣搜是圖論中的基礎演算法之一，屬於一種盲目搜尋方法。
廣搜需要使用隊列來實現，分以下幾步：
- 將起點插入隊尾；
- 取隊首 \(u\)，如果 $u\to v $ 有一條路徑，則將 \(v\) 插入隊尾；
- 如果隊列不為空，重複執行 \(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 過程中，隊列具有單調性。也就是說，隊列呈現這個樣子：
例題1 走迷宮
給出 \(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 最基本的應用。
例題2 山峰山谷
給定一個 \(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);
}
例題3 0/1 最短路
給出一張圖，其中每條邊的權值 \(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 的巧妙之處。
