簡介#
接下來要介紹的是 BFS (Breadth First Search) 廣度優先搜尋演算法，跟 DFS 很像的地方是都是用來走訪整張圖，不同的地方是搜尋的方式差很多。通常用來尋找無邊權圖的最短路。
廣度優先的意思就是，每次嘗試走訪同一層的節點，如果同一層都走訪完了，才會進到更深的下一層。
實作#
這邊就要用到前面章節的 queue：
bool vis[MAXN];
queue<int> q;
vis[1] = true;
q.push(1);
while (q.size()) {
int v = q.front();
q.pop();
for (auto u : g[v]) {
if (vis[u]) continue;
vis[u] = true;
q.push(u);
}
}
BFS 過程中紀錄訊息#
如果想知道起始點到每個點的最短距離，那你就可以多開一個 dist[] 陣列來儲存距離，每次進入一個新節點的時候就把距離更新成上一個節點的距離 +1 就行了：
bool vis[MAXN];
int dist[MAXN];
queue<int> q;
vis[1] = true;
dist[1] = 0;
q.push(1);
while (q.size()) {
int v = q.front();
q.pop();
for (auto u : g[v]) {
if (vis[u]) continue;
vis[u] = true;
// 更新成上個節點的距離 +1
dist[u] = dist[v] + 1;
q.push(u);
}
}
二維平面上的 BFS#
實作方式其實跟DFS中介紹的二維平面上 DFS 差不多，這邊只展示程式碼就不做太多敘述，比較值得注意的部分只有 queue 改成存 x y 座標的 pair：
// 對於每個方向的移動
int dx[4] = {1, -1, 0, 0};
int dy[4] = {0, 0, 1, -1};
bool vis[MAXN][MAXM];
queue<pair<int, int>> q;
vis[1][1] = true;
q.push({1, 1});
while (q.size()) {
auto [x, y] = q.front();
q.pop();
for (int i = 0; i < 4; i++) {
// 移動到新的座標
int nx = x + dx[i];
int ny = y + dy[i];
// 超出邊界或是已經走過就忽略
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
if (vis[nx][ny]) continue;
// 標記成走過
vis[nx][ny] = true;
// 繼續 BFS
q.push({nx, ny});
}
}
