アルゴリズム・データ構造図鑑 · 入門

幅優先探索:辺の本数が少ない順に進む

キューと訪問済み管理により、重みなしグラフの最短経路を求める。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 同じ距離の頂点を先に処理する
  2. 小さなグラフのキューを追う
  3. 発見時に印を付ける
  4. 最短距離の意味と限界
  5. 経路は前駆頂点から復元する
  6. 複数始点と到達不能な頂点
  7. この記事をロゲイアに質問する理解を確かめる

同じ距離の頂点を先に処理する

幅優先探索(BFS)は、始点から辺を0本、1本、2本…とたどって到達する頂点の順に探索します。最初に始点をキューへ入れ、先頭から頂点を取り出して、まだ発見していない隣接頂点を末尾へ加えます。先入れ先出しの順序により、近い層の処理が遠い層より先に進みます。各辺の重みが同じときは、最初に発見した距離が始点からの最短の辺数になります。

小さなグラフのキューを追う

辺A→B、A→C、B→D、C→Dを考えます。Aから始め、隣をB、Cの順に見るなら、キューは[A]から[B,C]へ変わります。Bを取り出すとDを発見し、キューは[C,D]です。CからDを見ても、既に発見済みなので追加しません。Dの距離は2で、Bを親として保存すればA→B→Dを復元できます。隣接頂点の列挙順が変わると選ばれる経路は変わり得ますが、最短の辺数は変わりません。

処理残るキュー新たな距離
Aを処理[B,C]B=1、C=1
Bを処理[C,D]D=2
Cを処理[D]Dは発見済み
Dを処理[]変更なし

発見時に印を付ける

訪問済みの印は、通常、キューへ入れる時点で付けます。取り出す時点まで印を付けないと、複数の親から同じ頂点が何度も追加されることがあります。隣接リスト表現では各頂点を一度取り出し、各辺を一定回数調べるため、全体を対象とする時間はO(V+E)、距離や親やキューの補助領域はO(V)です。隣接行列で全候補を走査する実装なら、辺を調べるコストの評価も変わります。

python
from collections import deque

def distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance

最短距離の意味と限界

BFSで最小化するのは辺の本数です。たとえばA→Dの重みが100、A→B→Dの各辺の重みが1なら、BFSは1本の経路を先に見つけますが、総重みは最小ではありません。重み付き問題ではDijkstra法など、条件に合う別の方法を使います。到達できない頂点は未発見のままであり、経路がないことを示す値を距離0と区別して保持します。複数の始点を最初から距離0で入れれば、最も近い始点からの距離も計算できます。

経路は前駆頂点から復元する

距離だけでなく経路も必要なら、頂点を初めて発見したとき、どの頂点から来たかを前駆頂点として記録します。ゴールDの前駆がB、Bの前駆がAなら、D、B、Aと逆向きにたどり、最後に列を反転するとA→B→Dを得られます。距離が2という数値だけでは、途中のBを復元できません。到達不能なゴールでは前駆も未設定のままなので、復元処理を始める前に到達したかを確認します。同じ長さの経路が複数ある場合、この手順が返すのは列挙順に応じた一つです。すべての最短経路を求めるには、前駆を一つだけ保存する方式とは異なる表現と出力費用が必要になります。

Python
from collections import deque

def bfs(graph, start):
    distance = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph.get(u, []):
            if v not in distance:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return distance, parent

複数始点と到達不能な頂点

複数の始点から最も近い距離を求めるには、すべての始点を距離0として最初にキューへ入れます。同じ始点の重複は除き、そこから通常のBFSを行うと、どれかの始点までの最小辺数が得られます。どの始点からも到達できない頂点には、距離0ではなく未到達という状態を残します。隣接行列で全候補を走査する実装では、隣接リストのO(V+E)という費用をそのまま使えません。巨大なグラフではキューが一つの広い層を保持するため、深さだけでなく幅によるメモリ使用も検討します。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ