BFS

簡介

接下來要介紹的是 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});
    }
}