幅優先探索(BFS)：最短経路の復元と訪問済みチェックの落とし穴

2026年11月改訂： この記事は2021年に韓国語で書いたBFSの解説を、日本語向けに書き直したものです。当時の例を Apple clang 21（Apple M1 Pro）で -Wall -Wextra と -fsanitize=address,undefined を付けてコンパイルし直したところ、迷路の例は宣言していない変数 min のせいでコンパイルできず、訪問済みの印をキューから取り出すときに付けていたため、10×10の空のグリッドでは固定長のキューがあふれて何も出力しませんでした。図はすべて描き直し、経路の復元と隣接リスト・行列の実測を追加しています。

AtCoderの迷路問題のように「最小の移動回数」を求めたい人、そしてBFSを書けるけれど訪問済みチェックをなぜその位置に置くのか説明しにくい人に向けた記事です。結論から書くと、BFSはキューから1つ取り出し、まだ見ていない隣接頂点に印を付けながらキューに入れる、の繰り返しです。入れる時点で印を付ければ各頂点はちょうど1回しかキューに入らず、最初にたどり着いたときの距離がそのまま最短距離になります。

深さ優先探索との違いは、同じグラフを使った深さ優先探索(DFS)の記事で比べています。キューを自作したい場合は連結リストで作るキューの記事を参照してください。

キューで1層ずつ広げる探索

BFS（Breadth First Search）は、始点から距離1の頂点をすべて訪れてから距離2、距離3と広げていきます。この順番を守らせるのがキュー（FIFO）です。先に見つけた頂点が先に出てくるので、距離1の頂点が出尽くすまで距離2の頂点は出てきません。「スタックにすればDFS、キューにすればBFS」とよく言われますが、半分だけ正しい話で、訪問済みチェックの位置も変えないと本当のDFSにはなりません。その様子はDFSの記事で実際の出力を見せています。

例として、頂点8個・辺10本のグラフを使います。辺は 1-2, 1-3, 1-4, 2-5, 3-5, 3-6, 4-7, 5-8, 6-8, 7-8 で、隣接頂点は番号の小さい順に調べます。

// BFS on an adjacency list, marking vertices when they are enqueued.
#include <cstdio>
#include <queue>
#include <vector>

int main() {
    const int n = 8;  // vertices 1..8
    const int edges[][2] = {{1,2},{1,3},{1,4},{2,5},{3,5},{3,6},{4,7},{5,8},{6,8},{7,8}};
    std::vector<std::vector<int>> adj(n + 1);
    for (auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);
    }
    std::vector<int> dist(n + 1, -1), parent(n + 1, 0);
    std::queue<int> q;
    dist[1] = 0;
    q.push(1);
    while (!q.empty()) {
        int v = q.front(); q.pop();
        std::printf("visit %d (dist %d) queue after:", v, dist[v]);
        for (int w : adj[v]) {
            if (dist[w] == -1) {          // not seen yet
                dist[w] = dist[v] + 1;    // mark NOW, at enqueue time
                parent[w] = v;
                q.push(w);
            }
        }
        auto copy = q;
        while (!copy.empty()) { std::printf(" %d", copy.front()); copy.pop(); }
        std::printf("\n");
    }
    std::vector<int> path;
    for (int v = 8; v != 0; v = parent[v]) path.push_back(v);
    std::printf("path to 8:");
    for (auto it = path.rbegin(); it != path.rend(); ++it) std::printf(" %d", *it);
    std::printf("  (%d edges)\n", dist[8]);
}

clang++ -std=c++20 -Wall -Wextra -fsanitize=address,undefined で警告なしにビルドし、実行した結果です。各行は頂点を1つ処理した直後のキューの中身です。

visit 1 (dist 0) queue after: 2 3 4
visit 2 (dist 1) queue after: 3 4 5
visit 3 (dist 1) queue after: 4 5 6
visit 4 (dist 1) queue after: 5 6 7
visit 5 (dist 2) queue after: 6 7 8
visit 6 (dist 2) queue after: 7 8
visit 7 (dist 2) queue after: 8
visit 8 (dist 3) queue after:
path to 8: 1 2 5 8  (3 edges)

3を処理するとき、隣の5はすでに2から見つかって距離が決まっているので入れ直しません。6と7も8をもう一度入れません。キューに入った回数は頂点数と同じ8回です。

dist 配列が訪問済みフラグを兼ねている点にも注目してください。-1ならまだ見ていない頂点、値が入っていればキューに入れたか処理済みの頂点です。別に visited 配列を持って同期させる必要はありません。

最短経路：長さだけでなく経路を復元する

辺の重みがすべて同じなら、BFSで最初に到達したときの距離が最短距離です。距離kの頂点が残っている間は、距離k+1の頂点がキューの先頭に来ないからです。2021年の記事は長さだけを出力していましたが、実務では「どう行くか」が必要な場面のほうが多いはずです。やり方は配列1つで済みます。キューに入れるときどこから来たか（親）を記録し、最後にゴールから親を逆にたどります。

新しく迷路を作って試しました。# が壁、S がスタート、G がゴールで、上下左右にだけ動けます。

// Shortest path on a grid maze with BFS, then rebuild the path from parent links.
#include <cstdio>
#include <queue>
#include <string>
#include <vector>

int main() {
    std::vector<std::string> g = {
        "S..#.......",
        ".#.#.#####.",
        ".#...#...#.",
        ".####.#.#..",
        "...#..#.#.#",
        ".#.#.##.#..",
        ".#.....#..G",
    };
    const int H = (int)g.size(), W = (int)g[0].size();
    int sr = 0, sc = 0, gr = 0, gc = 0;
    for (int r = 0; r < H; r++)
        for (int c = 0; c < W; c++) {
            if (g[r][c] == 'S') { sr = r; sc = c; }
            if (g[r][c] == 'G') { gr = r; gc = c; }
        }
    std::vector<int> dist(H * W, -1), parent(H * W, -1);
    std::queue<int> q;
    dist[sr * W + sc] = 0;
    q.push(sr * W + sc);
    const int dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1};
    int pushes = 1;
    while (!q.empty()) {
        int cur = q.front(); q.pop();
        if (cur == gr * W + gc) break;            // first time we pop G = shortest
        int r = cur / W, c = cur % W;
        for (int k = 0; k < 4; k++) {
            int nr = r + dr[k], nc = c + dc[k];
            if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue;
            int nxt = nr * W + nc;
            if (g[nr][nc] == '#' || dist[nxt] != -1) continue;
            dist[nxt] = dist[cur] + 1;
            parent[nxt] = cur;
            q.push(nxt);
            pushes++;
        }
    }
    int goal = gr * W + gc;
    if (dist[goal] == -1) { std::puts("no path"); return 1; }
    for (int v = parent[goal]; v != sr * W + sc; v = parent[v]) {
        g[v / W][v % W] = '*';
    }
    for (auto& row : g) std::puts(row.c_str());
    std::printf("moves: %d, cells on path: %d, enqueued: %d of %d cells\n",
                dist[goal], dist[goal] + 1, pushes, H * W);
}

実行結果です。* が復元した経路です。

S**#*******
.#*#*#####*
.#***#...#*
.####.#.#**
...#..#.#*#
.#.#.##.#*.
.#.....#.*G
moves: 22, cells on path: 23, enqueued: 43 of 77 cells

書いていて気づいた実務上のポイントです。

• 座標を r * W + c の整数1つにすると、dist と parent がただの1次元配列になります。2021年のコードは x・y・長さを3本の配列で別々に持っていました。
• 到達できない場合を明示的に扱う。 2021年のコードは経路がないと何も出力せずに終わっていました。上のコードは no path を出して終了コード1を返すので、スクリプトから判定できます。
• 「移動回数」と「マス数」を区別する。 2021年のコードはスタートのマスを1と数え、6×6の迷路の答えを13としていましたが、移動回数では12です。問題がどちらを聞いているかで+1するかを決めます。競プロの問題文ではここで1ずれる例をよく見かけます。

訪問済みは入れるときに：重複pushを数えてみた

2021年の迷路のコードは、マスをキューから取り出すときに訪問済み（map[y][x] = 0）にしていました。これだと、あるマスがキューで待っている間に、別の隣接マスが同じマスをもう一度入れられます。仕組みは次の図のとおりです。

どれくらい増えるのか、空の n×n グリッドで角から角まで、3通りの書き方で数えました。(1) 2021年の書き方（取り出し時に印、重複もそのまま展開）、(2) 取り出し時に印を付けるが、処理済みのマスは取り出した直後に捨てる、(3) 入れるときに印。clang -O2 でビルドしています。

(1) はマスの数ではなく最短経路の本数に比例して増えます。各マスはそこへ至る最短経路の本数だけキューに入り、10×10の全マスについて足すと C(20, 10) − 1 = 184,755 で、実測値とぴったり一致します。3通りとも距離は同じ値（19マス）を返すので、小さなテスト入力ではバグに気づけません。(2) は正しく爆発もしませんがpushが約2倍で、マスごとにちょうど1回になるのは (3) だけです。

2021年のコードでは、この重複がメモリ破壊につながっていました。キューが int x[100], y[100], l[100] という固定長配列だったからです。10×10の空のグリッドを入れると、UBSanがすぐに検出します。

bfs2fix.c:8:5: runtime error: index 100 out of bounds for type 'int[100]'
bfs2fix.c:9:5: runtime error: index 100 out of bounds for type 'int[100]'
bfs2fix.c:10:5: runtime error: index 100 out of bounds for type 'int[100]'

サニタイザなしでビルドすると（-O0 でも -O2 でも）、経路があるのに何も出力せず終了コード0で終わりました。シンボルの配置を見ると l の直後に map が置かれていて、l[100] への書き込みが迷路そのものを上書きしていました。2021年の記事は最後に「配列をキューとして使うとメモリを食うので、キューは自作したほうがよい」と書いていましたが、本当の原因は配列ではなく印を付ける位置でした。入れるときに印を付ければ各マスは1回しか入らないので、H×W 要素の配列キューで足ります。

隣接リストと隣接行列：N=10,000で実測

2021年のコードは int map[30][30] の隣接行列を使っていました。頂点が少なければ問題ありませんが、行列のBFSは頂点を1つ取り出すたびに行全体（N要素）を調べるので O(N²) です。隣接リストは実在する辺だけを見るので O(N+E) です。

頂点10,000・辺20,000（平均次数4）の連結グラフを作り、始点を変えながら各方式でBFSを20回ずつ回しました。行列は1マス1バイト（unsigned char）です。Apple M1 Pro、clang -O2、3回実行した結果です。

両方の距離が一致することはプログラム内で確認しています。速度は約60〜135倍、メモリは約230倍の差でした。2021年のコードのように int で持つと 10,000×10,000×4バイト = 400MB になります。行列が向いているのは、頂点が数百程度で辺が密な場合や、「uとvはつながっているか」をO(1)で頻繁に聞きたい場合くらいです。

2021年のコードの検証結果

2021年の記事の例2つをそのままコンパイルした結果をまとめます。

• 例1（隣接行列のBFS）：-Wall -Wextra で警告0、元の入力に対する出力も記事と同じでした。ただし map[30][30] なので頂点番号は29までです。頂点30を入れると UBSan が index 30 out of bounds for type 'int[30][30]' を報告します。また入力の最後の -1 -1 を忘れると、scanf が失敗してもループが終わらず無限ループになりました（3秒後に強制終了して確認）。scanf の戻り値は確認すべきです。
• 例2（迷路の最短経路）：error: use of undeclared identifier 'min' でコンパイル失敗。DFSの記事のコードから紛れ込んだ min = n * n; の1行でした。この行を消すと元の入力で記事と同じ「13」が出て、そのときのpushは24回でした。ほかは上で見た重複pushと配列のあふれです。コメントの「キューの最後の要素が最短経路の長さ」も誤りで、実際に出力しているのは最後の要素ではなくいま取り出した（pos 位置の）要素の長さです。

元の記事の図（グラフ、キューの状態、迷路のマス）は、すべてこの記事で新しく描いた図と実際の実行結果に置き換えました。

BFSを選ぶ場面

BFSは再帰しないので、グラフがどれだけ長くてもコールスタックはあふれません。そのかわりキューに1層分がまるごと入るので、幅の広いグラフではキューのメモリが増えます。1000×1000の空のグリッドでは、入れるときに印を付ける方式でキューの最大は1,000マスでした。迷路の最短経路をDFSで求めるとどれだけ遅くなるかは、DFSの記事で7×7のグリッドを使って実測しています。