BFS（幅優先探索）

始点から近い順に頂点を探索するアルゴリズム。 重みなしグラフの最短距離や到達可能性を求められる。

特徴

項目	内容
用途	最短距離、到達可能性
適用条件	重みなし（または全辺同一コスト）
計算量	O(V+E)
空間計算量	O(V+E)（グラフを含む）

実装の使い分け

• 軽量版：単一始点の最短距離を手軽に求める
• struct版：多始点BFSや経路復元も利用する

実装

軽量版

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

int main() {
    int n, m, s;
    cin >> n >> m >> s;
    vector<vector<int>> g(n);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
    }

    // s: 始点, dist: 始点からの距離, g: 隣接リスト
    vector<int> dist(n, -1);
    queue<int> q;
    dist[s] = 0;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int to : g[v]) {
            if (dist[to] != -1) continue;
            dist[to] = dist[v] + 1;
            q.push(to);
        }
    }

    for (int v = 0; v < n; v++) cout << dist[v] << '\n';
}

struct版

#pragma once
#include <algorithm>
#include <queue>
#include <vector>

struct BFS {
    int n;
    std::vector<std::vector<int>> g;
    std::vector<int> dist;
    std::vector<int> parent;

    BFS(int n) : n(n), g(n) {}

    // 無向辺を追加
    void add_edge(int u, int v) {
        g[u].push_back(v);
        g[v].push_back(u);
    }

    // 有向辺を追加
    void add_directed_edge(int u, int v) {
        g[u].push_back(v);
    }

    // 単一始点BFS
    void run(int s) {
        run(std::vector<int>{s});
    }

    // 多始点BFS
    void run(const std::vector<int>& sources) {
        dist.assign(n, -1);
        parent.assign(n, -1);
        std::queue<int> q;

        for (int s : sources) {
            if (dist[s] != -1) continue;
            dist[s] = 0;
            q.push(s);
        }

        while (!q.empty()) {
            int v = q.front();
            q.pop();
            for (int to : g[v]) {
                if (dist[to] != -1) continue;
                dist[to] = dist[v] + 1;
                parent[to] = v;
                q.push(to);
            }
        }
    }

    // 最後のrun()の始点からtへの経路を復元
    // 到達不能なら空配列
    std::vector<int> restore_path(int t) const {
        if (t < 0 || t >= n) return {};
        if (dist.empty() || dist[t] == -1) return {};
        std::vector<int> path;
        for (int v = t; v != -1; v = parent[v]) path.push_back(v);
        std::reverse(path.begin(), path.end());
        return path;
    }
};

使用例

軽量版

入力（0-indexed、有向グラフ）

4 3 0
0 1
1 2
0 3

出力

0
1
2
1

struct版：単一始点

BFS bfs(5);
bfs.add_edge(0, 1);
bfs.add_edge(1, 2);
bfs.add_edge(2, 3);
bfs.add_edge(3, 4);

bfs.run(0);

cout << bfs.dist[4] << '\n'; // 4

auto path = bfs.restore_path(4);
// path = {0, 1, 2, 3, 4}

struct版：多始点

bfs.run(vector<int>{0, 4});

cout << bfs.dist[2] << '\n'; // 2

複数の始点を距離0として探索する。 各頂点から最も近い始点までの距離を求められる。

注意点

• 訪問済み判定は dist[to] != -1 で行う
• 頂点をキューに入れるときに訪問済みにする
• 到達不能な頂点の距離は -1
• 最短経路の復元には parent を記録する
• 複数の最短経路がある場合、復元されるのはそのうちの1つ
• 多始点BFSの経路復元は、いずれかの最も近い始点までの経路になる
• 重みが異なる場合はDijkstraなどを検討する

関連アルゴリズム

• Dijkstra：非負辺重みの最短経路
• 0-1 BFS：辺重みが0または1の最短経路
• DFS：深さ優先探索