グラフのトラバーサルアルゴリズム — BFS・DFS・Dijkstra を「発明」する思考法

BFS・DFS・Dijkstra を知らない状態で「グラフのすべての頂点を訪れたい」という問題から出発すると、3 つのアルゴリズムは次の順に組み上がります。まず、サイクルで同じ頂点を回り続けないように訪問済みの記録 (visited) を持ちます。次に、見つけた頂点をキューで近い順に処理すると BFS、スタックで深い順に処理すると DFS になります。辺に重みがあるときは、キューを距離順の優先度付きキューに替えると Dijkstra 法になります。

それぞれのデータ構造がなぜ必要になるのかが分かれば、手順を覚えていなくても同じ考え方で組み立て直せます。

まず、問題を定義する

アルゴリズムを考える前に、何を解きたいのかを決めます。

素朴な問い: 「すべての場所を訪れたい」

見知らぬ街に放り出されたとします。地図はありませんが、今いる場所からどの道が伸びているかは見えます。すべての場所を漏れなく訪れるには、どう歩けばよいでしょうか。

これがグラフ探索（トラバーサル）の問題です。

街を抽象化して、交差点を頂点、道路を辺と呼びます。頂点と辺の集合がグラフです。

グラフ G = (V, E)
  V: 頂点の集合 {A, B, C, D}
  E: 辺の集合   {(A,B), (A,C), (B,C), (B,D), (C,D)}

現実の多くの問題がグラフで表現できます。

• 道路ネットワーク: 交差点が頂点、道路が辺
• SNS: ユーザーが頂点、友達関係が辺
• Web: ページが頂点、リンクが辺
• 依存関係: パッケージが頂点、依存が辺

辺に方向がつくと有向グラフ（一方通行の道路）、コスト（距離や時間）がつくと重み付きグラフになります。どちらでも、頂点から辺をたどって隣へ移るという探索の基本は変わりません。

グラフの表現: まず「隣人を知る」仕組みを作る

次に、グラフをプログラムでどう持つかを決めます。ここでも、必要な操作から逆算します。

探索で最も頻繁に行う操作は「ある頂点の隣接頂点を列挙する」ことです。これが速くできる表現を選びます。

隣接リスト — 「この人の友達は誰？」

各頂点について、隣にいる頂点の一覧を持ちます。疎なグラフ（辺が少ないグラフ）に向いています。

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C', 'D'],
    'C': ['A', 'B', 'D'],
    'D': ['B', 'C']
}

空間は $O(V + E)$、隣接頂点の列挙は $O(\text{degree})$ です。この記事の探索アルゴリズムは、すべて隣接リストを前提にしています。

隣接行列 — 「この 2 人は友達？」

$V \times V$ の表を作り、辺があれば 1 を入れます。特定の 2 頂点間に辺があるかを $O(1)$ で判定できますが、空間は $O(V^2)$ 必要です。

#     A  B  C  D
matrix = [
    [0, 1, 1, 0],  # A
    [1, 0, 1, 1],  # B
    [1, 1, 0, 1],  # C
    [0, 1, 1, 0],  # D
]

思考実験 1: 最もナイーブな探索

グラフが与えられたとして、すべての頂点を訪れる方法を考えます。

最初の壁: 「同じ場所を何度も訪れてしまう」

まず思いつくのは「隣に行けるなら行く」という方法です。しかしグラフには、木と違ってサイクル（ループ）がありえます。A→B→C→A→B→… と同じ場所を回り続けてしまいます。

そこで、同じ頂点を二度訪れないように訪問済みの記録 (visited) を持ちます。

visited = set()  # これが無いと無限ループ

この visited は、この記事で扱う 3 つのアルゴリズムすべてに出てきます（Dijkstra では距離テーブル dist がその役を兼ねます）。グラフにサイクルがありうる以上、何らかの形で必要になる記録です。

次の問い: 「隣人が複数いるとき、どの順番で行く？」

頂点 A にいて、まだ訪れていない隣人が B と C の 2 つあるとします。B と C のどちらを先に訪れるか、そしてその先で見つけた頂点をいつ訪れるかで、2 つの戦略に分かれます。

BFS の発想 — 「遠くに行く前に、近場をすべて調べ尽くそう」

問題設定を変えてみる: 「一番近いコンビニはどこ？」

見知らぬ街で一番近いコンビニを探すなら、一本の道をどこまでも進むことはしないはずです。まず今いる場所のすぐ隣のブロックをすべて確認し、なければその外側のブロックへと、同心円状に範囲を広げていきます。

BFS（幅優先探索）はこの探し方をグラフで行います。

近い場所から順に調べれば、見つかった場所が最も近いと保証できる。

発想の核心: 「待ち行列」を使う

近い順の処理をどう実装するかを、始点 A から具体的に追ってみます。

1. A の隣人 B と C を「あとで調べるリスト」に入れる
2. B を調べる。B の隣人 D と E を「あとで調べるリスト」に追加する
3. D と E はすぐには調べず、先に C を調べる

C を先に調べるのは、C が D と E より先にリストに入ったからです。C は始点から距離 1、D と E は距離 2 です。BFS では先に発見した頂点ほど始点に近いので、先に入れたものを先に出すキュー（FIFO: First-In-First-Out）を使えば、近い順に処理できます。

なぜキューなら最短経路が保証されるのか

キューの FIFO 性により、距離 $d$ の頂点がすべて処理されてから、距離 $d+1$ の頂点が処理されます。

帰納法で確かめます。

1. 始点（距離 0）が最初に処理される ✓
2. 距離 $d$ の頂点が処理されるとき、その未発見の隣人（距離 $d+1$）がキューに追加される
3. キューの FIFO 性により、距離 $d$ の頂点がすべて処理されたあとに距離 $d+1$ の頂点が処理される
4. ある頂点 $v$ が距離 $d$ で初めて発見されたとき、もし $d$ より短い経路があれば、$v$ はそれより前のレベルで発見されているはずなので矛盾する

形式的には、キューの中の頂点の距離が先頭から末尾へ非減少で、先頭と末尾の差が高々 1 である、という不変条件が常に成り立ちます。

アルゴリズム

ここまでをコードにすると次のようになります。

from collections import deque
 
def bfs(graph, start):
    visited = set()        # 発見1: 同じ場所に二度行かない
    queue = deque([start]) # 発見2: 近い頂点を先に処理するためキューを使う
    visited.add(start)
    order = []
 
    while queue:
        vertex = queue.popleft()  # 先に入れたものを先に出す（FIFO）
        order.append(vertex)
 
        for neighbor in graph[vertex]:
            if neighbor not in visited:
                visited.add(neighbor)   # キューに入れた時点で「発見済み」
                queue.append(neighbor)
 
    return order

visited.add(neighbor) を呼ぶのは、キューに入れた時点です。取り出すまで印をつけないと、B と C がどちらも D の隣人の場合、B の処理時と C の処理時に同じ D が 2 回キューに入ります。発見した時点で印をつけるのは、この二重登録を防ぐためです。

ステップごとに見てみよう

下のビジュアライザーで BFS の動きを確認できます。

• キューの中身は常に始点から近い順に並ぶ
• 距離 1 の頂点がすべて処理されてから、距離 2 の頂点に進む
• 訪問済みの範囲が、波紋のように始点から広がっていく

BFS の計算量

• 時間計算量: $O(V + E)$ — 各頂点が 1 回ずつキューに入り、隣接リストの各要素が 1 回ずつ確認される
• 空間計算量: $O(V)$ — キューと visited 集合

DFS の発想 — 「まず一本道を最後まで行こう」

まったく別の問題設定: 「出口はあるか？」

次は「一番近い場所」ではなく、「この迷路に出口はあるか」「すべての部屋を調べ尽くせるか」という問題です。

迷路を歩く人は、たいてい次のように動きます。

1. 分岐点で 1 つの道を選び、行けるところまで進む
2. 行き止まりにぶつかったら、直前の分岐点まで戻る
3. 別の道を選んで、また行けるところまで進む
4. すべての道を試すまで繰り返す

最短かどうかは気にせず、すべての道を漏れなく調べる。これが DFS（深さ優先探索）です。

発想の核心: 「再帰」という自然な構造

この探索戦略は再帰でそのまま書けます。

頂点 $v$ にいるとき、$v$ の隣人をすべて探索します。隣人 $u$ を探索するとは、$u$ にいるときに $u$ の隣人をすべて探索することです。同じ問題が、1 つ先の頂点で繰り返されます。

explore(v):
  v を訪問済みにする
  v の各隣人 u について:
    u が未訪問なら explore(u) を呼ぶ

この再帰で、行けるところまで深く進み、行き止まりで引き返す動きになります。explore(u) が終わって制御が explore(v) に戻る部分が、バックトラック（引き返し）にあたります。

なぜ「スタック」なのか？ — 再帰とコールスタック

再帰を使わずに DFS を書こうとすると、スタックが必要な理由がわかります。

BFS ではキューに「あとで処理する頂点」を入れました。DFS でも同じように入れますが、最後に追加した頂点、つまり最も深い位置にある頂点を最初に処理します。最後に入れたものを最初に出すのはスタック（LIFO: Last-In-First-Out）です。再帰呼び出しも、内部ではコールスタックを使って同じことをしています。

BFS と DFS の中心的な違いは、次に処理する頂点をどちらの端から取り出すかです。

BFS: queue.popleft()  → 先に入れたもの（近い場所）を先に
DFS: stack.pop()      → 後に入れたもの（深い場所）を先に

取り出し方を変えると探索の順序が変わり、向いている問題も変わります（下のスタック版では、訪問済みの印をつけるタイミングも BFS と異なります）。

アルゴリズム（再帰版）

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
 
    visited.add(start)
    print(start)  # 頂点を処理
 
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)  # 再帰 = 深く潜る
 
    # ここに戻ってくる = バックトラック
    return visited

アルゴリズム（スタック版）

再帰の深さが問題になる場合は、明示的にスタックを使います。

def dfs_iterative(graph, start):
    visited = set()
    stack = [start]
    order = []
 
    while stack:
        vertex = stack.pop()  # 末尾から取り出す（LIFO）
        if vertex in visited:
            continue
        visited.add(vertex)
        order.append(vertex)
 
        for neighbor in reversed(graph[vertex]):
            if neighbor not in visited:
                stack.append(neighbor)
 
    return order

ステップごとに見てみよう

上のビジュアライザーを DFS モードに切り替えると、BFS との違いがわかります。

• コールスタックが一方向に深くなっていく
• 行き止まりで巻き戻しが起きる
• 訪問順序が BFS と異なり、近い頂点から順にはならない

発見時刻と完了時刻 — DFS がもたらす追加情報

DFS では、各頂点の発見時刻（いつ発見されたか）と完了時刻（いつ探索が完了したか）を記録できます。BFS にはない情報です。

time = 0
 
def dfs_with_timestamps(graph, vertex, visited, discovery, finish):
    global time
    time += 1
    discovery[vertex] = time  # 発見時刻
    visited.add(vertex)
 
    for neighbor in graph[vertex]:
        if neighbor not in visited:
            dfs_with_timestamps(graph, neighbor, visited, discovery, finish)
 
    time += 1
    finish[vertex] = time  # 完了時刻

有向非巡回グラフ（DAG）では、DFS の完了時刻の逆順がトポロジカルソートになります。辺 $u \to v$ を「$u$ を $v$ より先に処理する必要がある」という向きで張るなら、DAG の各辺について $\mathrm{finish}(u) > \mathrm{finish}(v)$ が成り立つため、完了時刻の逆順で $u$ が $v$ より前に来ます。サイクルがある場合、トポロジカル順序は存在しないので、DFS でサイクルを検出してエラーにする必要があります。

BFS と DFS の計算量は同じ

• 時間: $O(V + E)$
• 空間: $O(V)$

どちらも各頂点を 1 回、隣接リストの各要素を 1 回ずつ処理するので、計算量は同じです。違うのは処理する順序で、その違いによって向いている問題が変わります。

BFS と DFS を並べて比較する

2 つの戦略の使い分け — 問題の構造を見る

BFS は「距離」が重要な問題に使う:

• 最短経路（無重みグラフ）
• あるノードから $k$ ホップ以内の全ノード列挙
• 二部グラフ判定（グラフを 2 色で塗れるか？）

DFS は「構造」が重要な問題に使う:

• サイクル検出（有向グラフでは再帰スタック上の頂点に戻ったか？ 無向グラフでは親以外の訪問済み頂点にぶつかったか？）
• トポロジカルソート（完了時刻の逆順）
• 連結成分・強連結成分の分解
• バックトラッキング（パズル、制約充足問題）

近い順に広げたいなら BFS、1 本のパスを最後まで追いたいなら DFS です。

思考実験 2: 「BFS では解けない問題」に出会う

BFS で無重みグラフの最短経路が求まることはわかりました。次の問題はどうでしょうか。

「東京から大阪まで、もっとも所要時間が短いルートは？」

道路ごとに所要時間（重み）が違います。仮に、東京から大阪へ直行する道が 5 時間、東京→名古屋→大阪と 2 本の道を乗り継ぐと合計 4 時間だとします。

BFS は辺の本数（ホップ数）を最小化するので、1 本で着く直行ルート（5 時間）を選びます。辺の重みを考慮しないため、2 本を乗り継ぐ 4 時間のルートを見逃します。辺のコストが均一でないと、BFS では最短距離を保証できません。

そこで、BFS を重みに対応させる方法を考えます。

Dijkstra の発想 — BFS を「重み」に対応させる

思考のステップ 1: 「BFS は何を保証していたか」の再分析

BFS が正しく動く理由を振り返ります。

1. 距離 0 の頂点（始点だけ）を確定する
2. 距離 1 の頂点（始点の隣人すべて）を確定する
3. 距離 2 の頂点（距離 1 の頂点の隣人のうち未発見のもの）を確定する
4. …

キューの FIFO 性が、小さい距離から先に確定することを保証していました。

重み付きグラフでは、隣にいるからといって近いとは限りません。先ほどの例でも、東京から大阪へ直行する辺（5 時間）より、名古屋を経由する 2 辺の経路（合計 4 時間）の方が近くなります。

思考のステップ 2: 「距離でソートしたキュー」を使えば？

そこで、キューを距離の小さい順に並べることにします。FIFO キューの代わりに優先度付きキュー（プライオリティキュー）を使います。

• BFS: キュー（FIFO） → 発見が早い順 = 辺の本数が少ない順
• Dijkstra: 優先度付きキュー → 距離が小さい順 = 重みの合計が少ない順

BFS のキューを優先度付きキューに置き換えたものが Dijkstra 法です。

思考のステップ 3: 「最小距離の頂点は確定してよい」という洞察

優先度付きキューの先頭にある頂点 $u$ の距離を、確定してよい理由は次のとおりです。

優先度付きキューの先頭にある頂点 $u$ は、もうこれ以上短い経路では到達できない。なぜなら、まだ処理されていない頂点の距離はすべて $u$ の距離以上であり、辺の重みは非負なので、それらを経由しても距離は減らないから。

この論理が成り立つのは、辺の重みが非負のときだけです。負の辺があると、遠い頂点を経由して距離が減ることがあり、この論理は崩れます。負の辺がある場合は Bellman-Ford 法などを使います。

思考のステップ 4: 「緩和」という操作

確定した頂点 $u$ から辺をたどって隣人 $v$ を見たとき、$u$ を経由した方が $v$ に近ければ $v$ の距離を更新します。この操作を緩和（relaxation）と呼びます。

「緩和」は歴史的な用語で、制約 $d(v) \le d(u) + w(u, v)$ に由来すると説明されます。操作の中身は、$\infty$（無限大）から始めた距離の見積もり（上界）を、よりよい経路が見つかるたびに引き下げることです。

ここまでの思考をアルゴリズムにまとめる

import heapq
 
def dijkstra(graph, start):
    # graph: { node: [(neighbor, weight), ...] }
    dist = {node: float('inf') for node in graph}  # 最初はすべて∞
    prev = {node: None for node in graph}
    dist[start] = 0                                 # 始点だけ0
    pq = [(0, start)]  # 優先度付きキュー（BFSのキューの代わり）
 
    while pq:
        d, u = heapq.heappop(pq)  # 最小距離の頂点を取り出す（BFSのpopleftの代わり）
 
        if d > dist[u]:  # 古い情報はスキップ
            continue
 
        for v, weight in graph[u]:
            new_dist = dist[u] + weight
            if new_dist < dist[v]:  # 緩和: u経由の方が近いなら更新
                dist[v] = new_dist
                prev[v] = u
                heapq.heappush(pq, (new_dist, v))
 
    return dist, prev

BFS のコードと構造はほぼ同じです。変わったのは次の 3 点です。

1. キュー → 優先度付きキュー（距離順に取り出す）
2. visited → dist テーブル（訪問の有無だけでなく距離を管理）
3. 緩和チェックの追加（new_dist < dist[v]）

ステップごとに見てみよう

下のビジュアライザーでは、次の動きを確認できます。

• 一度設定した距離が、別の経路で更新される（これが緩和）
• 常に最小距離の頂点が選ばれて確定する
• 距離テーブルの prev 列が、最終的に最短経路木になる

Dijkstra の計算量

使うデータ構造で変わります。

• 二分ヒープ: $O((V + E) \log V)$。最も一般的
• フィボナッチヒープ: $O(V \log V + E)$。この 3 つの中では理論上の計算量が最も小さいが、実装が複雑
• 配列（単純ループ）: $O(V^2)$。辺が $V^2$ に近い密グラフでは、二分ヒープより速い

3 つのアルゴリズムの進化を振り返る

出発点: 「グラフのすべての頂点を漏れなく訪れたい」

発見1 — visited: サイクルで無限ループしないよう、訪問済み記録が必要

分岐 — 「どの順番で？」:

• 「近い場所から順に」→ FIFO キュー → BFS
• 「一本道を深くまで」→ LIFO スタック / 再帰 → DFS

発展 — 「辺に重みがある場合は？」:

• BFS のキューを優先度付きキューに置き換え → Dijkstra
• 「最小距離の頂点は確定してよい」+ 緩和操作が核心

DFS は BFS と違う問い（すべての道を調べたい）から、Dijkstra は BFS が重みを扱えないという限界から出てきました。どちらも、新しい問いや条件に対して前の方法の何が合わないかを見極めるところから始まっています。

応用例: 発想がどう活きるか

トポロジカルソート — DFS の副産物

ビルドシステムで「libA は libB に依存」「libB は libC に依存」というとき、ビルド順序を決める問題です。

DAG なら、DFS の完了時刻の逆順を取ればビルド順序が得られます。依存先から依存元へ辺を張ると「libC → libB → libA」となり、完了時刻の逆順からビルド順序 C → B → A が得られます。サイクルが見つかった場合、トポロジカル順序は存在しません。

def topological_sort(graph):
    visited = set()
    result = []
 
    def dfs(node):
        visited.add(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)
        result.append(node)  # 完了時に追加
 
    for node in graph:
        if node not in visited:
            dfs(node)
 
    return result[::-1]  # 逆順が答え

二部グラフ判定 — BFS の層構造を活用

隣接する頂点が同じ色にならないように、グラフの頂点を 2 色で塗り分けられるかを判定する問題です。BFS のレベルごとの処理を使い、偶数レベルと奇数レベルで色を交互に塗ります。

def is_bipartite(graph):
    color = {}
    for start in graph:
        if start in color:
            continue
        queue = deque([start])
        color[start] = 0
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if neighbor not in color:
                    color[neighbor] = 1 - color[node]
                    queue.append(neighbor)
                elif color[neighbor] == color[node]:
                    return False  # 同色の隣接 = 二部グラフではない
    return True

計算量まとめ

おわりに — 3 つのアルゴリズムを導いた手順

3 つのアルゴリズムは、どれも同じ手順で導きました。

1. 問題を定義する: 何を求めたいのかを決める
2. ナイーブな解を考える: まず最も単純な方法を試し、どこでうまくいかないかを見る
3. ボトルネックを特定する: サイクルで回り続ける → visited、訪れる順序 → データ構造の選択
4. データ構造で解決する: キュー、スタック、優先度付きキューのどれを使うかで戦略が決まる
5. 正当性を検証する: なぜ正しいのか、どんな条件で壊れるのかを確かめる（Dijkstra と負の辺）

近い順に処理したいならキュー、深く進みたいならスタック、重みを考慮したいなら優先度付きキュー。BFS・DFS・Dijkstra は、この対応からそれぞれ導けます。教科書にない問題でも、この 5 つの手順をたどれば、使うべきデータ構造の見当をつけられます。