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

この記事は、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 はすべてのグラフ探索アルゴリズムに共通する、最も基本的な構成要素です。当たり前に見えますが、これは「グラフにはサイクルがある」という問題の構造を分析した結果生まれる発想です。

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

頂点 A にいて、まだ訪れていない隣人が B と C の両方いる。B を先に訪れるか、C を先に訪れるか？ ここで2つの対照的な戦略が分岐します。

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

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

もしあなたが見知らぬ街で「一番近いコンビニ」を探しているとしたら、どうしますか？

いきなり一本の道をどこまでも突き進んだりはしませんよね。まず今いる場所のすぐ隣のブロックをすべて確認し、見つからなければその次のブロック…と、同心円状に範囲を広げていくのが自然な発想です。

これがBFS（幅優先探索）の根本的な発想です:

「近い場所を先に調べれば、見つかったときにそれが最短だと保証できる」

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

この「近い順に処理する」をどう実現するか？ ここが設計上の核心です。

思考実験をしてみましょう。あなたは始点 A にいます:

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

なぜ C を先に？ C は B や D, E より先に「あとで調べるリスト」に入ったからです。C は始点に近い（距離1）のに対し、D と E は始点から遠い（距離2）。距離が近い頂点を先に処理したいなら、先に入れたものを先に出す — つまりキュー（FIFO: First-In-First-Out）が必要です。

この気づきが BFS の本質です。「近い順に処理したい」→「発見が早い = 距離が近い」→「先に入れたものを先に出す」→「キューを使う」。

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

キューの FIFO 性により、距離 $d$ のすべての頂点が処理されてから、距離 $d+1$ の頂点が処理される — このレベル単位の処理順序が保証されます。

これは帰納法で考えると明確です:

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

形式的には不変条件 $d(v) \leq d(u) + 1$（$u$ は $v$ を発見した頂点）が常に成り立ちます。

アルゴリズム

ここまでの思考をコードにすると:

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) はキューに入れた瞬間であって、取り出した瞬間ではありません。なぜか？ もし取り出すまで visited にしなければ、B と C がどちらも D の隣人の場合、B の処理時にも C の処理時にも同じ D がキューに入ってしまいます。「発見した時点で印をつける」のは、二重登録を防ぐためです。

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

下のビジュアライザで BFS の動きを見てください。注目してほしいのは:

• キューの中身が常に「距離の近い順」に並んでいること
• 距離1の頂点がすべて処理されてから距離2に進むこと
• これが「波紋」のパターンであること

BFS の計算量

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

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

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

ここで問題を変えてみましょう。「一番近い場所」ではなく、「この迷路に出口はあるか？」「すべての部屋を探索し尽くせるか？」 という問題を考えます。

迷路で行き詰まった人間は本能的にこう動きます:

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

「最短」は気にしない。とにかくすべての道を漏れなく調べたい — この戦略が DFS（深さ優先探索）です。

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

DFS の巧みさは、この探索戦略が再帰で極めて自然に記述できることです。

ある頂点 $v$ にいるとき、「$v$ のすべての隣人を探索する」ことを考えます。隣人 $u$ を探索するとは何か？ 「$u$ にいるとき、$u$ のすべての隣人を探索する」ことです。これは全く同じ問題の再帰的な定義になっています。

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

この再帰構造が「行けるところまで深く進み、行き止まりで自然に引き返す」動きを生み出します。explore(u) が終わって制御が explore(v) に戻ってくる — これがバックトラック（引き返し）です。

なぜ「スタック」なのか？ — 再帰の本質

再帰を使わない場合に DFS を実装するとどうなるか考えると、DFS のデータ構造がなぜスタックなのかがわかります。

BFS ではキューに「あとで処理する頂点」を入れました。DFS でも同様に「あとで処理する頂点」を入れるのですが、最後に追加したもの（＝最も深い位置にあるもの）を最初に処理したいのです。「最後に入れたものを最初に出す」— つまりスタック（LIFO: Last-In-First-Out）です。

BFS と DFS の違いは、コード上ではたった一箇所です:

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

データ構造を一つ入れ替えるだけで、探索の性質が根本的に変わる — これがアルゴリズム設計の美しさです。

アルゴリズム（再帰版）

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 とはまったく異なる訪問順序になること
• 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  # 完了時刻

なぜこれが有用なのか？ 完了時刻の逆順はトポロジカルソート（依存関係の順序）になります。辺 $u \to v$ がある場合、$v$ は $u$ より先に完了します（$v$ を訪問し終わってから $u$ に戻るため）。完了の逆順にすると $u$ が $v$ より先になり、「$v$ が $u$ に依存」つまり「$u$ を先に処理する」順序が得られます。

ビルドシステムで「libA は libB に依存」「libB は libC に依存」というときに、ビルド順序を C → B → A と決定する — これが DFS の完了時刻から自然に導かれるのです。

BFS と DFS の計算量は同じ

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

計算量が同じなのは当然です。どちらも「各頂点を1回、各辺を1回」処理するからです。違うのは処理する順序だけ。そしてその順序の違いが、解ける問題を全く変えるのです。

BFS と DFS を並べて比較する

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

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

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

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

• サイクル検出（探索中に訪問済み頂点にぶつかったか？）
• トポロジカルソート（完了時刻の逆順）
• 連結成分・強連結成分の分解
• バックトラッキング（パズル、制約充足問題）

本質的に: 「近い順に広げたい」→ BFS、「一本のパスを最後まで追いたい」→ DFS。

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

ここまでで BFS を使えば無重みグラフの最短経路が解けることがわかりました。

では次の問題はどうでしょう:

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

道路ごとに所要時間（重み）が異なります。東名高速は4時間、中央道は5時間、新幹線は2.5時間…。

BFS をそのまま適用すると何が起きるか？ BFS は「辺の本数」＝ホップ数を最小化しますが、辺の重みを考慮しません。2辺を通るルートの方が1辺のルートより短い場合がありえます（例: 東京→名古屋→大阪 = 4h が、東京→大阪直行 = 5h より短い）。

BFS の限界: 辺のコストが均一でないと、最短距離を保証できない。

これが「BFS を拡張して、重みを考慮できるアルゴリズムはないか？」という問いにつながります。

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

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

BFS が正しく動く理由を振り返りましょう:

1. 距離0の頂点を確定 → 始点だけ
2. 距離1の頂点を確定 → 始点の隣人すべて
3. 距離2の頂点を確定 → 距離1の頂点の隣人すべて
4. …

キューの FIFO 性が「小さい距離を先に確定」を保証していました。

重み付きグラフでは、「隣にいる＝近い」とは限りません。直行の辺（重み5）より、2辺経由（重み2+1=3）の方が近いことがありえます。

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

ここで自然に思いつくアイデア: キューを「距離の小さい順」にソートすればいいのでは？ つまり、FIFO キューの代わりに優先度付きキュー（プライオリティキュー）を使う。

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

BFS のキューを優先度付きキューに置き換える — これが Dijkstra の核心的な発想です。

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

でも、なぜこれが正しいのか？ 優先度付きキューの先頭にある頂点 $u$ の距離は本当に「確定」して良いのか？

ここが Dijkstra の最も深い洞察です:

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

この論理が成り立つのは辺の重みが非負のとき限定です。もし負の辺があると、遠い頂点を経由することで距離が減りうるため、この論理が崩壊します。（負の辺がある場合は Bellman-Ford アルゴリズムが必要になります。）

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

確定した頂点 $u$ から辺を辿って隣人 $v$ を見たとき、「$u$ を経由した方が $v$ に近いなら、$v$ の距離を更新する」 — これを緩和（relaxation）と呼びます。

なぜ「緩和」という名前なのか？ 距離の見積もりを「$\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 のコードと見比べてください。構造はほぼ同じで、変わったのは:

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

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

下のビジュアライザで、特に以下に注目してください:

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

Dijkstra の計算量

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

• 二分ヒープ: $O((V + E) \log V)$ — 最も一般的
• フィボナッチヒープ: $O(V \log V + E)$ — 理論的に最速だが実装が複雑
• 配列（単純ループ）: $O(V^2)$ — 辺が多い密グラフでは逆に効率的

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

ここまでの思考の道筋を整理しましょう:

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

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

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

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

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

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

それぞれのアルゴリズムは前のアルゴリズムの限界から生まれています。問題の構造を分析し、「何が足りないか」を特定することが、次のアルゴリズムの発想につながるのです。

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

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

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

DFS を発想の起点にすると: 「DFS の完了時刻の逆順を取ればよい」ことに気づきます。辺 $u \to v$ がある場合、$v$ は $u$ より先に DFS が完了する。逆順にすれば $u$ が先 — これが依存関係の正しい順序です。

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

計算量まとめ

おわりに — アルゴリズムを「再発明」できる力

この記事で追体験してきた思考プロセスをまとめます:

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

BFS・DFS・Dijkstra は空から降ってきた魔法ではなく、「近い順に処理したい → キュー」「深く潜りたい → スタック」「重みを考慮したい → 優先度付きキュー」という論理的な帰結です。

この思考法を身につければ、教科書に載っていない問題に出会ったときにも、同じプロセスで自分のアルゴリズムを「発明」できるようになるはずです。