多視点BFS (Multi-Source BFS) の基本と実装例

多視点BFS (Multi-Source BFS) の基本と実装例

こんにちは。 CaseLabの立ち上げをしつつ、競技プログラミングでアルゴリズムの学習を進めている勝俣です。このブログでは、学んだ内容を整理し、自分なりに言語化して共有しています。

今回は「多視点BFS (Multi-Source BFS)」についてまとめてみます。
単一の始点からのBFS (Breadth-First Search) は、よく知られたグラフ探索手法ですが、
複数の始点を同時に考える「多視点BFS」は、特定の問題で便利なテクニックとなります。

多視点BFSとは

通常のBFSは、1つの始点（頂点）から探索を始めますが、多視点BFSでは、
「複数の始点」を同時に探索キューに入れて、同じようにレベル（距離）を広げていきます。

例えば、以下のような状況で役立ちます。

• 複数の初期感染者（感染源）がいる感染拡大シミュレーション
• 複数の避難口から最短到達時間を求める問題
• 複数の目標地点からの最短距離が必要な問題

いずれも、始点が1つであれば単純なBFSを複数回行うことが可能ですが、
複数の始点を一度に扱うことで、計算を効率化したり、コードをシンプルに書ける場合があります。

Python的な発想からC++での実装へ

Pythonでは、collections.deque を使ってBFSを実装することが多く、
queue に複数の初期地点を一気に append することで多視点BFSを簡潔に表現できます。

C++では std::queue を使い、複数の初期地点を最初から push しておくことで同様のことが可能です。
コード全体としては、複数の始点を距離0として初期化し、それらを最初からキューに入れて、
通常のBFSループを回せば、同時に距離が拡がっていくことになります。

実装例（C++）

ここでは、迷路または格子状のグラフを想定した、多視点BFSのサンプルを示します。
（実際にはグラフなら adj リスト、迷路なら grid を使うなど、問題に応じて変えることになります）

問題設定例

• H x W のグリッドがあります。
• 一部のセルが「始点」となります（複数個所）。
• 通れるマスと通れないマス（例：壁 #）があり、通れるマス上で「各マスまでの最短距離」を求めます。
• 通れないマスには到達不可能として距離は -1 のままです。

ポイント

• 多視点BFSは、「最初のキュー投入段階で複数の始点を距離0として登録する」ことで、
  その後の探索を1回のBFSループで行える点が特長です。
• 普段は1つの始点から行うBFSを、全始点を一括でキューに入れるだけで、同時に波紋が広がるように探索が進みます。
• 再利用性を考え、BFSの処理部分を関数化しておくと、他の問題に応用しやすくなります。
  例えば、違うマップに対して同じロジックを用いる、
  または始点や移動可能条件のみを変えて使い回すことが可能になります。

コードサンプル（C++）

#include <bits/stdc++.h>
using namespace std;

/**
 * @brief 多視点BFSを行い、各セルまでの最短距離を求める関数。
 * 
 * @param H グリッドの高さ
 * @param W グリッドの幅
 * @param grid グリッド（H行W列）。'#'が壁、他は通過可能とする。
 * @param starts 複数の始点座標 (row, col) のベクター
 * @return vector<vector<int>> 各セルまでの最短距離を格納した2次元配列
 *                            到達不可能なセルは -1 となる。
 */
vector<vector<int>> multi_source_bfs(int H, int W, const vector<string> &grid, const vector<pair<int,int>> &starts) {
    // dist配列を初期化(-1で未訪問を表す)
    vector<vector<int>> dist(H, vector<int>(W, -1));

    // 多視点BFS用のキュー
    queue<pair<int,int>> que;

    // 全ての始点をキューに投入し、距離0で初期化
    for (auto &st : starts) {
        dist[st.first][st.second] = 0;
        que.push(st);
    }

    // 方向ベクトル（上下左右）
    int dx[4] = {1, -1, 0, 0};
    int dy[4] = {0, 0, 1, -1};

    // BFSループ開始
    while (!que.empty()) {
        auto [x, y] = que.front();
        que.pop();

        for (int k = 0; k < 4; k++) {
            int nx = x + dx[k];
            int ny = y + dy[k];

            // 範囲チェック
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;

            // 壁マス('#')は通れないのでスキップ
            if (grid[nx][ny] == '#') continue;

            // すでに訪問済みならスキップ
            if (dist[nx][ny] != -1) continue;

            // 未訪問で通れるマスなら距離を更新
            dist[nx][ny] = dist[x][y] + 1;
            que.push({nx, ny});
        }
    }

    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 入力受け取り
    int H, W;
    cin >> H >> W;
    vector<string> grid(H);
    for (int i = 0; i < H; i++) {
        cin >> grid[i];
    }

    // 複数の始点を探し、ベクターに格納
    vector<pair<int,int>> starts;
    // ここでは 'S' と書かれたマスを始点とみなす
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (grid[i][j] == 'S') {
                starts.push_back({i,j});
            }
        }
    }

    // 多視点BFS実行
    vector<vector<int>> dist = multi_source_bfs(H, W, grid, starts);

    // 結果出力（各マスの距離を空白区切りで表示）
    // 到達不能なマスは -1 のまま
    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            cout << dist[i][j] << (j == W - 1 ? '\n' : ' ');
        }
    }

    return 0;
}

コードサンプル（Python）

from collections import deque

def multi_source_bfs(H, W, grid, starts):
    """
    多視点BFSを行い、各セルまでの最短距離を求める関数。
    
    Parameters
    ----------
    H : int
        グリッドの高さ
    W : int
        グリッドの幅
    grid : list of str
        グリッド（H行W列）。'#'が壁、他は通過可能とする。
    starts : list of (int, int)
        複数の始点座標 (row, col)

    Returns
    -------
    dist : list of list of int
        各セルまでの最短距離を格納した2次元リスト。
        到達不可能なセルは -1 となる。
    """
    # dist配列を初期化(-1で未訪問を表す)
    dist = [[-1] * W for _ in range(H)]

    # 多視点BFS用のキュー
    que = deque()

    # 全ての始点をキューに投入し、距離0で初期化
    for x, y in starts:
        dist[x][y] = 0
        que.append((x, y))

    # 方向ベクトル（上下左右）
    directions = [(1,0), (-1,0), (0,1), (0,-1)]

    # BFSループ開始
    while que:
        x, y = que.popleft()

        for dx, dy in directions:
            nx, ny = x + dx, y + dy

            # 範囲チェック
            if not (0 <= nx < H and 0 <= ny < W):
                continue

            # 壁マス('#')は通れないのでスキップ
            if grid[nx][ny] == '#':
                continue

            # すでに訪問済みならスキップ
            if dist[nx][ny] != -1:
                continue

            # 未訪問で通れるマスなら距離を更新
            dist[nx][ny] = dist[x][y] + 1
            que.append((nx, ny))

    return dist

if __name__ == "__main__":
    # 入力受け取り
    H, W = map(int, input().split())
    grid = [input().strip() for _ in range(H)]

    # 複数の始点を探し、リストに格納
    starts = []
    # ここでは 'S' と書かれたマスを始点とみなす
    for i in range(H):
        for j in range(W):
            if grid[i][j] == 'S':
                starts.append((i, j))

    # 多視点BFS実行
    dist = multi_source_bfs(H, W, grid, starts)

    # 結果出力（各マスの距離を空白区切りで表示）
    # 到達不能なマスは -1 のまま
    for i in range(H):
        print(' '.join(map(str, dist[i])))