0-1 BFSとは？C++で学ぶ重み0/1グラフの最短経路探索アルゴリズム

0-1 BFS（二値重みグラフの最短経路問題）とは

いくつかの頂点と辺から構成されるグラフを考えます。このグラフの各辺には0または1の二値のみの重みが割り当てられています。始点となる頂点が与えられたとき、始点から他のすべての頂点への最短距離を求めるのが本記事の目的です。

通常の幅優先探索（BFS）は、すべての辺の重みが同一である場合に有効な手法です。しかし、重みが0と1で混在している場合、単純なBFSでは正しい最短経路を求めることができません。

そこで登場するのが0-1 BFSです。このアルゴリズムでは、両端キュー（deque）を使用して頂点を管理します。各ステップで最適な距離条件をチェックしながら、辺の重みに応じて次のように頂点を挿入します。

• 辺の重みが0の場合 → キューの先頭（front）に挿入
• 辺の重みが1の場合 → キューの末尾（back）に挿入

この工夫により、キュー内の距離の単調性が保たれ、ダイクストラ法と同等の結果をO(V+E)という高速な計算量で得ることができます。

アルゴリズム

binaryBFS(src) の流れは以下の通りです。

begin
    dist配列を定義し、始点から頂点iへの距離をdist[i]に格納する（初期値は無限大）
    dist[src] := 0
    srcをキューQに挿入する
    while Qが空でない間、繰り返す
        v := Qの先頭要素を取り出し、削除する
        for vに接続するすべての辺eについて
            if dist[v] + 辺(v,i)の重み < dist[隣接頂点i] then
                 距離を更新する
                 if 重みが0なら先頭に挿入、そうでなければ末尾に挿入
            end if
        done
    done
    dist配列のすべての距離を出力する
end

C++による実装例

以下は、上記アルゴリズムをC++で実装した完全なサンプルコードです。

#include<iostream>
#include<vector>
#include<deque>
#define V 8
using namespace std;

struct node {
    int next, weight;
};

vector<node> edges[V];

void binaryBFS(int src) {
    int dist[V];
    for (int i = 0; i < V; i++) // 初期値は無限大として設定
        dist[i] = INT_MAX;
    deque<int> Q;
    dist[src] = 0; // 始点から始点自身への距離は0
    Q.push_back(src);
    while (!Q.empty()) {
        int v = Q.front(); // 先頭の頂点を取り出す
        Q.pop_front();
        for (int i = 0; i < edges[v].size(); i++) {
            // 最適な距離かどうかをチェック
            if (dist[edges[v][i].next] > dist[v] + edges[v][i].weight) {
                dist[edges[v][i].next] = dist[v] + edges[v][i].weight;
                // 重み0の辺は先頭へ、重み1の辺は末尾へ挿入
                if (edges[v][i].weight == 0)
                    Q.push_front(edges[v][i].next);
                else
                    Q.push_back(edges[v][i].next);
            }
        }
    }
    for (int i = 0; i < V; i++)
        cout << dist[i] << " ";
}

void addEdge(int u, int v, int wt) {
    edges[u].push_back({v, wt});
    edges[v].push_back({u, wt}); // 無向グラフとして双方向に登録
}

int main() {
    addEdge(0, 1, 0);
    addEdge(0, 3, 1);
    addEdge(0, 4, 0);
    addEdge(1, 2, 1);
    addEdge(1, 7, 0);
    addEdge(2, 5, 1);
    addEdge(2, 7, 0);
    addEdge(3, 4, 0);
    addEdge(3, 6, 1);
    addEdge(4, 6, 1);
    addEdge(5, 7, 1);
    addEdge(6, 7, 1);
    int src = 6; // 始点は頂点6
    binaryBFS(src);
}

出力結果

1 1 1 1 1 2 0 1

この出力は、始点である頂点6から各頂点（0〜7）への最短距離を表しています。例えば、頂点6自身の距離は0、頂点5への距離は2となっていることが分かります。

計算量とポイントまとめ

• 時間計算量： O(V+E) — ダイクストラ法（O(E log V)）よりも高速
• 空間計算量： O(V+E) — 隣接リストとキューの分
• 核心のアイデア： 重み0の辺で更新された頂点は「同じ距離レベル」とみなしてキュー先頭へ、重み1の辺は次の距離レベルとして末尾へ挿入することで、キュー内の距離を常にソート済みの状態に保つ

0-1 BFSは、迷路問題やグリッド上のコスト付き移動など、辺の重みが小さな整数値に限定される場面で特に威力を発揮するテクニックです。ぜひ実装して理解を深めてください。