跳转至

BFS（圖論）

BFS 全稱是 Breadth First Search，中文名是寬度優先搜索，也叫廣度優先搜索。

是圖上最基礎、最重要的搜索算法之一。

所謂寬度優先。就是每次都嘗試訪問同一層的節點。 如果同一層都訪問完了，再訪問下一層。

這樣做的結果是，BFS 算法找到的路徑是從起點開始的 最短 合法路徑。換言之，這條路徑所包含的邊數最小。

在 BFS 結束時，每個節點都是通過從起點到該點的最短路徑訪問的。

算法過程可以看做是圖上火苗傳播的過程：最開始只有起點着火了，在每一時刻，有火的節點都向它相鄰的所有節點傳播火苗。

實現

下文中 C++ 與 Python 的代碼實現是基於鏈式前向星的存圖方式，其實現可參考 圖的存儲 頁面。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
bfs(s) {
  q = new queue()
  q.push(s), visited[s] = true
  while (!q.empty()) {
    u = q.pop()
    for each edge(u, v) {
      if (!visited[v]) {
        q.push(v)
        visited[v] = true
      }
    }
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void bfs(int u) {
  while (!Q.empty()) Q.pop();
  Q.push(u);
  vis[u] = 1;
  d[u] = 0;
  p[u] = -1;
  while (!Q.empty()) {
    u = Q.front();
    Q.pop();
    for (int i = head[u]; i; i = e[i].nxt) {
      if (!vis[e[i].to]) {
        Q.push(e[i].to);
        vis[e[i].to] = 1;
        d[e[i].to] = d[u] + 1;
        p[e[i].to] = u;
      }
    }
  }
}

void restore(int x) {
  vector<int> res;
  for (int v = x; v != -1; v = p[v]) {
    res.push_back(v);
  }
  std::reverse(res.begin(), res.end());
  for (int i = 0; i < res.size(); ++i) printf("%d", res[i]);
  puts("");
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from queue import Queue

def bfs(u):
    Q = Queue()
    Q.put(u)
    vis[u] = True
    d[u] = 0
    p[u] = -1
    while Q.qsize() != 0:
        u = Q.get()
        i = head[u]
        while i:
            if vis[e[i].to] == False:
                Q.put(e[i].to)
                vis[e[i].to] = True
                d[e[i].to] = d[u] + 1
                p[e[i].to] = u
            i = e[i].nxt

def restore(x):
    res = []
    v = x
    while v != -1:
        res.append(v)
        v = p[v]
    res.reverse()
    for i in range(0, len(res)):
        print(res[i])

具體來説，我們用一個隊列 Q 來記錄要處理的節點，然後開一個布爾數組 vis[] 來標記是否已經訪問過某個節點。

開始的時候，我們將所有節點的 vis 值設為 0，表示沒有訪問過；然後把起點 s 放入隊列 Q 中並將 vis[s] 設為 1。

之後，我們每次從隊列 Q 中取出隊首的節點 u，然後把與 u 相鄰的所有節點 v 標記為已訪問過並放入隊列 Q。

循環直至當隊列 Q 為空，表示 BFS 結束。

在 BFS 的過程中，也可以記錄一些額外的信息。例如上述代碼中，d 數組用於記錄起點到某個節點的最短距離（要經過的最少邊數），p 數組記錄是從哪個節點走到當前節點的。

有了 d 數組，可以方便地得到起點到一個節點的距離。

有了 p 數組，可以方便地還原出起點到一個點的最短路徑。上述代碼中的 restore 函數使用該數組依次輸出從起點到節點 x 的最短路徑所經過的節點。

時間複雜度 \(O(n + m)\)

空間複雜度 \(O(n)\)（vis 數組和隊列）

open-closed 表

在實現 BFS 的時候，本質上我們把未被訪問過的節點放在一個稱為 open 的容器中，而把已經訪問過了的節點放在一個稱為 closed 容器中。

在樹/圖上 BFS

BFS 序列

類似 DFS 序列，BFS 序列是指在 BFS 過程中訪問的節點編號的序列。

一般圖上 BFS

如果原圖不連通，只能訪問到從起點出發能夠到達的點。

BFS 序列通常也不唯一。

類似的我們也可以定義 BFS 樹：在 BFS 過程中，通過記錄每個節點從哪個點訪問而來，可以建立一個樹結構，即為 BFS 樹。

應用

  • 在一個無權圖上求從起點到其他所有點的最短路徑。
  • 在 \(O(n+m)\) 時間內求出所有連通塊。（我們只需要從每個沒有被訪問過的節點開始做 BFS，顯然每次 BFS 會走完一個連通塊）
  • 如果把一個遊戲的動作看做是狀態圖上的一條邊（一個轉移），那麼 BFS 可以用來找到在遊戲中從一個狀態到達另一個狀態所需要的最小步驟。
  • 在一個有向無權圖中找最小環。（從每個點開始 BFS，在我們即將抵達一個之前訪問過的點開始的時候，就知道遇到了一個環。圖的最小環是每次 BFS 得到的最小環的平均值。）
  • 找到一定在 \((a, b)\) 最短路上的邊。（分別從 a 和 b 進行 BFS，得到兩個 d 數組。之後對每一條邊 \((u, v)\)，如果 \(d_a[u]+1+d_b[v]=d_a[b]\)，則説明該邊在最短路上）
  • 找到一定在 \((a, b)\) 最短路上的點。（分別從 a 和 b 進行 BFS，得到兩個 d 數組。之後對每一個點 v，如果 \(d_a[v]+d_b[v]=d_a[b]\)，則説明該點在某條最短路上）
  • 找到一條長度為偶數的最短路。（我們需要一個構造一個新圖，把每個點拆成兩個新點，原圖的邊 \((u, v)\) 變成 \(((u, 0), (v, 1))\) 和 \(((u, 1), (v, 0))\)。對新圖做 BFS，\((s, 0)\) 和 \((t, 0)\) 之間的最短路即為所求）
  • 在一個邊權為 0/1 的圖上求最短路，見下方雙端隊列 BFS。

雙端隊列 BFS

如果你不瞭解雙端隊列 deque 的話，請參閲 deque 相關章節。

雙端隊列 BFS 又稱 0-1 BFS。

適用範圍

邊權值為可能有，也可能沒有（由於 BFS 適用於權值為 1 的圖，所以一般權值是 0 或 1），或者能夠轉化為這種邊權值的最短路問題。

例如在走迷宮問題中，你可以花 1 個金幣走 5 步，也可以不花金幣走 1 步，這就可以用 0-1 BFS 解決。

實現

一般情況下，我們把沒有權值的邊擴展到的點放到隊首，有權值的邊擴展到的點放到隊尾。這樣即可保證像普通 BFS 一樣整個隊列隊首到隊尾權值單調不下降。

下面是偽代碼：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
while (隊列不為空) {
  int u = 隊首;
  彈出隊首;
  for (枚舉 u 的鄰居) {
    更新數據
    if (...)
      添加到隊首;
    else
      添加到隊尾;
  }
}

例題

Codeforces 173B

一個 \(n \times m\) 的圖，現在有一束激光從左上角往右邊射出，每遇到 '#'，你可以選擇光線往四個方向射出，或者什麼都不做，問最少需要多少個 '#' 往四個方向射出才能使光線在第 \(n\) 行往右邊射出。

此題目正解不是 0-1 BFS，但是適用 0-1 BFS，減小思維強度，賽時許多大佬都是這麼做的。

做法很簡單，一個方向射出不需要花費（0），而往四個方向射出需要花費（1），然後直接來就可以了。

代碼

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;

#define INF (1 << 29)
int n, m;
char grid[1001][1001];
int dist[1001][1001][4];
int fx[] = {1, -1, 0, 0};
int fy[] = {0, 0, 1, -1};
deque<int> q;  // 双端队列

void add_front(int x, int y, int dir, int d) {  // 向前方加
  if (d < dist[x][y][dir]) {
    dist[x][y][dir] = d;
    q.push_front(dir);
    q.push_front(y);
    q.push_front(x);
  }
}

void add_back(int x, int y, int dir, int d) {  // 向后方加
  if (d < dist[x][y][dir]) {
    dist[x][y][dir] = d;
    q.push_back(x);
    q.push_back(y);
    q.push_back(dir);
  }
}

int main() {
  cin >> n >> m;
  for (int i = 0; i < n; i++) cin >> grid[i];

  for (int i = 0; i < n; i++)
    for (int j = 0; j < m; j++)
      for (int k = 0; k < 4; k++) dist[i][j][k] = INF;

  add_front(n - 1, m - 1, 3, 0);

  while (!q.empty()) {  // 具体搜索的过程，可以参考上面写的题解
    int x = q[0], y = q[1], dir = q[2];
    q.pop_front();
    q.pop_front();
    q.pop_front();
    int d = dist[x][y][dir];
    int nx = x + fx[dir], ny = y + fy[dir];
    if (nx >= 0 && nx < n && ny >= 0 && ny < m)
      add_front(nx, ny, dir, d);  // 判断条件
    if (grid[x][y] == '#')
      for (int i = 0; i < 4; i++)
        if (i != dir) add_back(x, y, i, d + 1);
  }
  if (dist[0][0][3] == INF)
    cout << -1 << endl;
  else
    cout << dist[0][0][3] << endl;
  return 0;
}

優先隊列 BFS

優先隊列，相當於一個二叉堆，STL 中提供了 std::priority_queue，可以方便我們使用優先隊列。

在基於優先隊列的 BFS 中，我們每次從隊首取出代價最小的結點進行進一步搜索。容易證明這個貪心思想是正確的，因為從這個結點開始擴展的搜索，一定不會更新原來那些代價更高的結點。換句話説，其餘那些代價更高的結點，我們不回去考慮更新它。

當然，每個結點可能會被入隊多次，只是每次入隊的代價不同。當該結點第一次從優先隊列中取出，以後便無需再在該結點進行搜索，直接忽略即可。所以，優先隊列的 BFS 當中，每個結點只會被處理一次。

相對於普通隊列的 BFS，時間複雜度多了一個 \(\log n\)，畢竟要維護這個優先隊列嘛。不過普通 BFS 有可能每個結點入隊、出隊多次，時間複雜度會達到 \(O(n^2)\)，不是 \(O(n)\)。所以優先隊列 BFS 通常還是快的。

誒？這怎麼聽起來這麼像堆優化的 Dijkstra 算法呢？事實上，堆優化 Dijkstra 就是優先隊列 BFS。

習題

雙端隊列 BFS：

參考

https://cp-algorithms.com/graph/breadth-first-search.html

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：Ir1d, greyqz, yjl9903, Anguei, Marcythm, ChungZH, Xeonacid, ylxmf2005
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用