グラフ探索アルゴリズム入門 - BFS・DFS・ダイクストラと最短経路
グラフアルゴリズムの網羅的な定番教科書。
競プロ視点でグラフ探索を実践的に学べる。
日本語でグラフ・DPを丁寧に解説する良書。
当サイトは Amazon.co.jp を宣伝しリンクすることで紹介料を得る手段を提供する、Amazonアソシエイト・プログラムの参加者です。価格・在庫はリンク先の最新情報をご確認ください。
「駅Aから駅Bまで最短何回の乗り換えで行けるか」「タスクの依存関係をどんな順番で片づければ矛盾がないか」「地図上の2地点を結ぶ最短ルートはどれか」——こうした問題は、見た目はバラバラでも、いずれもグラフという同じ道具で表現できます。グラフを「たどる（探索する）」ためのアルゴリズムが、この記事で扱う幅優先探索(BFS)・深さ優先探索(DFS)、そして重み付きの最短経路を求めるダイクストラ法などです。この記事では、グラフの用語と表現から始めて、代表的な探索アルゴリズムの仕組み・計算量・実務での使い所までを、Pythonのコード例を交えて整理します。歴史的な出典や計算量は、原論文やWikipediaを確認したうえで記載しています。
グラフとは（頂点・辺・有向/無向・重み）
グラフとは、頂点（vertex, node）の集合と、頂点どうしをつなぐ辺（edge）の集合からなるデータ構造です。頂点を丸、辺を線で描くと直感的に理解できます。慣習として頂点数を V、辺数を E と書き、計算量もこの2つで表します。
辺には次のような種類があります。
- 無向グラフ: 辺に向きがない。「AとBは友達」のような対称な関係を表す
- 有向グラフ: 辺に向きがある。「AはBをフォローしている」のような一方向の関係を表す
- 重み付きグラフ: 辺にコスト（距離・時間・料金など）が付いている。地図の道路や通信ネットワークのレイテンシなど
さらに、途中で同じ頂点に戻ってくる経路を閉路（cycle）と呼び、閉路を持たない有向グラフをDAG（有向非巡回グラフ, Directed Acyclic Graph）と呼びます。DAGはタスクの依存関係やビルドの順序付けなどで頻繁に登場する重要な形です。
グラフの表現（隣接リストと隣接行列）
グラフをプログラムで扱うには、まず「どの頂点とどの頂点が辺でつながっているか」をデータとして持つ必要があります。代表的な表現は2つです。
隣接リスト（adjacency list）は、各頂点について「隣接する頂点の一覧」を持つ方式です。多くの実問題ではグラフが疎（辺が頂点数に対して少ない）なので、メモリ効率が良く、探索でも隣接頂点を素直に列挙できるため、最もよく使われます。
# 無向グラフを隣接リストで表現する
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C", "E"],
"E": ["D"],
}隣接行列（adjacency matrix）は、V 行 V 列の表を用意し、頂点 i と頂点 j の間に辺があるかどうかを各マスに記録する方式です。2頂点間の辺の有無を一定時間で判定できる反面、辺が少なくても必ず V^2 個分のメモリを消費します。
両者の特性を比較すると次のようになります。
| 観点 | 隣接リスト | 隣接行列 |
|---|---|---|
| 空間計算量 | O(V+E) | O(V^2) |
| 2頂点間の辺の有無 | O(次数) | O(1) |
| ある頂点の隣接頂点の列挙 | O(次数) | O(V) |
| 向いている状況 | 疎なグラフ・大規模グラフ | 密なグラフ・辺の有無を頻繁に問い合わせる場合 |
一般には、実務で扱うグラフは疎であることが多いため、隣接リストが第一候補になります。以降のコード例もすべて隣接リストを前提とします。なお、この O(V+E) や O(V^2) といった記法に不安がある方は、先に計算量とBig-O記法 入門を読んでおくと理解がスムーズです。
幅優先探索 BFS（キューで近い順にたどる）
幅優先探索（Breadth-First Search, BFS）は、始点に近い頂点から順に、いわば「波紋が広がるように」外側へ探索していく方法です。始点から距離1の頂点をすべて見てから距離2へ、次に距離3へと進みます。実装にはキュー（FIFO, 先入れ先出し）を使い、訪問済みの頂点を集合で管理して二度訪れないようにします。
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft() # 先に入れたものから取り出す
order.append(node)
for nxt in graph[node]:
if nxt not in visited:
visited.add(nxt)
queue.append(nxt)
return orderBFSの最大の特長は、重みなしグラフにおける最短経路（最小ステップ数）を求められる点です。近い順に広げていくので、ある頂点に初めて到達したときの距離が、そのまま始点からの最短距離になります。距離も同時に記録するには、次のように書きます。
from collections import deque
def bfs_distance(graph, start):
dist = {start: 0}
queue = deque([start])
while queue:
node = queue.popleft()
for nxt in graph[node]:
if nxt not in dist: # 未到達なら
dist[nxt] = dist[node] + 1 # 1ステップ遠い
queue.append(nxt)
return dist先ほどの graph を始点 A で探索すると、次のような結果になります。
探索順（BFS）: A, B, C, D, E
始点Aからの最短距離: A=0, B=1, C=1, D=2, E=3計算量は、各頂点を一度ずつ取り出し、各辺を（無向なら両方向で）一度ずつ調べるため O(V+E) です。訪問済み管理をハッシュ集合で行うと1回の判定が平均一定時間で済みます。この「集合による重複排除」の考え方はハッシュテーブル入門の応用でもあります。
BFSの歴史は意外に古く、一般に、Konrad Zuseが1945年のPlankalkülに関する（当時は未公刊の）博士論文で連結成分を求める手法として記述し、その後1959年にEdward F. Mooreが迷路の最短経路を解く文脈で独立に再発見したとされています。
深さ優先探索 DFS（行けるところまで進む）
深さ優先探索（Depth-First Search, DFS）は、BFSとは対照的に、行けるところまで一気に深く進み、行き止まったら一歩戻って別の道を試す方法です。迷路で片方の壁に手を当てて進み続けるイメージに近く、実装は再帰、あるいは明示的なスタック（LIFO, 後入れ先出し）で書けます。
def dfs(graph, start):
visited = set()
order = []
def visit(node):
visited.add(node)
order.append(node)
for nxt in graph[node]:
if nxt not in visited:
visit(nxt) # 隣へ深く潜る
visit(start)
return order再帰はスタックオーバーフローの懸念があるため、グラフが大きい場合は明示的なスタックを使う反復版が安全です。
def dfs_iterative(graph, start):
visited = set()
order = []
stack = [start]
while stack:
node = stack.pop() # 最後に入れたものから取り出す
if node in visited:
continue
visited.add(node)
order.append(node)
for nxt in reversed(graph[node]):
if nxt not in visited:
stack.append(nxt)
return orderDFSも計算量は O(V+E) ですが、用途はBFSと大きく異なります。深く潜る性質を活かして、次のような問題に使われます。
- 連結成分の数え上げ: 未訪問の頂点からDFSを繰り返し、何回始められたかで成分数がわかる
- 閉路の検出: 探索の途中で「今まさに探索中の頂点」に再び出会ったら閉路がある
- トポロジカルソート: DFSの帰りがけ（後行順）に頂点を積むと、依存順が得られる
DFSのアイデア自体は、19世紀のフランスの数学者Charles Pierre Trémauxによる迷路探索法までさかのぼれるとされ、計算機科学の文脈では1970年代にHopcroftとTarjanによって整理・一般化されました。特にRobert Tarjanは1972年に、DFSを用いて有向グラフの強連結成分を線形時間で求めるアルゴリズムを示しています。
トポロジカルソート（依存関係の順序付け）
トポロジカルソートは、DAGの頂点を「すべての辺が前から後ろへ向く」ように一列に並べる操作です。「AはBの前提」という依存が辺で表されているとき、矛盾なく実行できる順番を求める、という実務直結のテーマです。DFSの後行順を使う方法のほか、入次数0の頂点から取り除いていくKahnのアルゴリズムが有名です。
from collections import deque
def topological_sort(graph, nodes):
indeg = {v: 0 for v in nodes}
for v in nodes:
for w in graph[v]:
indeg[w] += 1 # 各頂点の入次数を数える
queue = deque([v for v in nodes if indeg[v] == 0])
order = []
while queue:
v = queue.popleft()
order.append(v)
for w in graph[v]:
indeg[w] -= 1 # v を取り除いた分、入次数を減らす
if indeg[w] == 0:
queue.append(w)
if len(order) != len(nodes):
raise ValueError("グラフに閉路があります（DAGではありません）")
return orderすべての頂点を並べきれずに終わった場合、そのグラフには閉路があり、トポロジカル順序は存在しません。この手法は、A. B. Kahnが1962年にCommunications of the ACM誌の論文「Topological sorting of large networks」で提示したもので、計算量は O(V+E) です。ビルドツールの依存解決、タスクスケジューラ、表計算の再計算順序などで日常的に使われています。
重み付き最短経路（ダイクストラ法）
辺に重み（距離やコスト）が付くと、「ステップ数が少ない経路」と「合計コストが小さい経路」は一致しなくなります。遠回りでも軽い辺を選んだほうが総コストが小さい、ということが起こるからです。非負の重みを持つグラフで単一始点から各頂点への最短コストを求める定番がダイクストラ法です。
考え方は「確定していない頂点のうち、暫定距離が最小のものを毎回選んで確定させる」という貪欲法です。最小のものを効率よく取り出すために優先度付きキュー（ヒープ）を使います。ヒープの内部構造そのものについてはソートアルゴリズム入門のヒープソートの節も参考になります。
import heapq
def dijkstra(graph, start):
# graph[u] = [(v, weight), ...] 重みは非負とする
INF = float("inf")
dist = {start: 0}
pq = [(0, start)] # (暫定距離, 頂点)
while pq:
d, u = heapq.heappop(pq) # 暫定距離が最小の頂点を取り出す
if d > dist.get(u, INF):
continue # 更新済みの古いエントリはスキップ
for v, w in graph[u]:
nd = d + w
if nd < dist.get(v, INF): # より短い経路を見つけたら緩和
dist[v] = nd
heapq.heappush(pq, (nd, v))
return dist次のような有向・重み付きグラフを始点 A で解いてみます。
入力グラフ（有向・重み付き）
A ->1 B, A ->4 C, B ->2 C, B ->5 D, C ->1 D, D ->3 E
始点Aからの最短距離
A: 0
B: 1
C: 3 （A -> B -> C = 1 + 2。直行の A -> C = 4 より短い）
D: 4 （A -> B -> C -> D = 1 + 2 + 1）
E: 7 （A -> B -> C -> D -> E = 1 + 2 + 1 + 3）二分ヒープを用いた実装の計算量は O((V+E) log V) です。より高度なフィボナッチヒープを使うと理論上は O(E + V log V) まで改善できますが、実装が複雑で定数倍も大きいため、実務では二分ヒープ（言語標準のヒープ）で十分なことがほとんどです。
ダイクストラ法は、Edsger W. Dijkstraが1959年の論文「A note on two problems in connexion with graphs」（Numerische Mathematik誌）で示した2つの問題のうちの1つ、最短経路問題への解として知られています。ネットワークのルーティングプロトコルOSPFの経路計算などにも応用されている、実務でも極めて重要なアルゴリズムです。
WARNING
ダイクストラ法は負の重みを持つ辺があると正しく動きません。一度確定した頂点はもう更新しないという前提が、負辺によって崩れるためです。負の辺があり得る場合は、次のベルマン–フォード法を使います。
ベルマン–フォードと A*（負辺・ヒューリスティック）
ベルマン–フォード法は、負の重みを含むグラフでも単一始点最短経路を求められるアルゴリズムです。すべての辺を対象に「緩和（より短い経路が見つかれば距離を更新する操作）」を V-1 回繰り返す、という素直な手続きで動きます。
def bellman_ford(edges, nodes, start):
# edges = [(u, v, weight), ...] weight は負でもよい
INF = float("inf")
dist = {v: INF for v in nodes}
dist[start] = 0
for _ in range(len(nodes) - 1): # V-1 回繰り返す
for u, v, w in edges:
if dist[u] != INF and dist[u] + w < dist[v]:
dist[v] = dist[u] + w # 緩和
for u, v, w in edges: # もう一度緩和できたら
if dist[u] != INF and dist[u] + w < dist[v]:
raise ValueError("負の閉路が存在します")
return dist計算量は O(VE) とダイクストラ法より重いものの、負の辺を扱え、さらに負の閉路（回るほどコストが下がってしまう循環）の検出までできるのが強みです。歴史的には、Lester Ford Jr.（1956年）とRichard Bellman（1958年）にちなんで名付けられ、Edward F. Mooreの貢献も知られることからベルマン–フォード–ムーア法と呼ばれることもあります。
一方、A*（エースター）は、始点から終点への最短経路を効率よく求めるために、ダイクストラ法にヒューリスティック（目的地までの推定コスト）を組み合わせたアルゴリズムです。「今までのコスト」に「ゴールまでの推定残りコスト」を足した値が小さい頂点を優先することで、無駄な方向への探索を減らします。推定値がゴールまでの真のコストを決して過大評価しない（許容的である）とき、A*は最短経路を保証します。A*は、Peter Hart、Nils Nilsson、Bertram Raphaelの3名が1968年の論文「A Formal Basis for the Heuristic Determination of Minimum Cost Paths」で提示しました。ゲームの経路探索やカーナビなど、ゴールが明確な問題で広く使われています。
計算量まとめ（比較表）
ここまで登場したアルゴリズムを、用途・計算量・重みへの対応で整理します。計算量はいずれも隣接リスト表現を前提とし、ダイクストラ法は二分ヒープ実装の値です。
| アルゴリズム | 主な用途 | 計算量 | 重み対応 | 負の辺 |
|---|---|---|---|---|
| BFS | 重みなし最短ステップ数・連結成分 | O(V+E) | 非対応 | 非対応 |
| DFS | 連結成分・閉路検出・トポロジカルソート | O(V+E) | 非対応 | 非対応 |
| トポロジカルソート(Kahn) | DAGの順序付け | O(V+E) | 対象外 | 対象外 |
| ダイクストラ法 | 単一始点の重み付き最短経路 | O((V+E) log V) | 対応 | 非対応 |
| ベルマン–フォード法 | 単一始点最短経路・負閉路検出 | O(VE) | 対応 | 対応 |
| A* | 単一始点・単一終点の最短経路 | ヒューリスティック依存 | 対応 | 非対応 |
選び方の指針はシンプルです。重みがなければBFS、重みがあり負辺がなければダイクストラ法、負辺があり得るならベルマン–フォード法、ゴールが1点で良い推定値を作れるならA*、という順で候補を絞ると迷いにくくなります。
実務での使い所
グラフ探索は、一見グラフに見えない問題の中に潜んでいることが多く、「これはグラフだ」と気づけるかどうかが応用の分かれ目になります。
- 経路探索・ナビゲーション: 地図やゲームマップの最短ルートはダイクストラ法やA*の典型的な出番です。交差点が頂点、道路が重み付きの辺になります
- 依存関係の解決: ビルドシステム、パッケージマネージャ、タスクスケジューラは、依存をDAGとして表しトポロジカルソートで実行順を決めます。閉路検出は「循環依存」の検出そのものです
- ネットワーク・分散システム: ルーティングプロトコルは最短経路アルゴリズムに支えられています。負荷分散の設計を考える際にも、経路やコストをグラフで捉える視点が役立ちます（ロードバランシングのアルゴリズム入門）
- SNSや推薦: 「友達の友達」「n次のつながり」はBFSで距離を測る問題です。到達可能性の判定にはDFSやBFSが使えます
なお、頂点数が数億に達するような巨大グラフでは、訪問済み集合そのものがメモリを圧迫します。厳密さを少し犠牲にして省メモリで「見たことがあるか」を判定したい場面では、ブルームフィルタ入門で扱うような確率的データ構造が選択肢になることもあります。
NOTE
実装を一から書く機会は多くありません。多くの言語やライブラリに最短経路やトポロジカルソートの実装が用意されています。大切なのは、目の前の問題をグラフとして定式化し、どのアルゴリズムが適合するかを計算量と制約（重み・負辺・ゴールの有無）から判断できることです。
まとめ
- グラフは頂点と辺からなり、有向/無向・重みの有無で扱うアルゴリズムが変わる。表現は疎なグラフに強い隣接リストが基本
- BFSはキューで近い順にたどり、重みなしの最短ステップ数を
O(V+E)で求められる - DFSは深く潜る性質を活かし、連結成分・閉路検出・トポロジカルソートに使える。計算量は同じく
O(V+E) - 重み付きの最短経路は、非負ならヒープを使うダイクストラ法（
O((V+E) log V)）、負辺があるならベルマン–フォード法（O(VE)） - ゴールが定まっているなら、推定コストで探索を絞るA*が効率的
- 実務では「これはグラフだ」と定式化できることが第一歩。あとは重み・負辺・ゴールの有無で道具を選ぶ
まずは身近な問題——乗り換え、依存関係、地図——を頂点と辺で描いてみるところから始めてみてください。定式化さえできれば、あとはこの記事の道具を当てはめるだけです。
