グラフ探索アルゴリズム大全：BFS/DFSから最短経路・A*までの理論と実装ガイド
エバープレイ編集部はじめに — グラフ探索アルゴリズムとは
グラフ探索アルゴリズムとは、ノード（頂点）とエッジ（辺）で構成されるグラフ構造に対して、到達可能性の判定、経路の発見、最短経路の計算、構造解析などを行う一連の手法を指します。ITでは、ネットワーク解析、ルーティング、マップ検索、依存関係解析、Webクローリング、ゲームAIなど幅広い分野で用いられます。グラフは有向／無向、重み付き／非重み付き、循環の有無など多様な形態を取り、探索アルゴリズムは問題の性質に応じて選択・調整されます。
基本アルゴリズム：BFS と DFS
最も基本的な探索は幅優先探索（BFS: Breadth-First Search）と深さ優先探索（DFS: Depth-First Search）です。
- BFS：キューを用いて、スタート頂点から距離（エッジ数）順に探索します。無重みグラフでの最短経路（エッジ数最小）を保証します。時間計算量は O(V + E)、メモリは最悪で探索フロンティアのサイズに依存します。
- DFS：スタック（再帰）で奥へ深く進み、行き止まりでバックトラックします。経路の列挙、帰納的構造の検査、トポロジカルソート（DAGの場合）や強連結成分分解の基礎として使われます。時間計算量は O(V + E)、メモリは再帰深さ O(V)（実際は深さ）です。
両者とも「訪問済み（visited）」セットを保持してループや重複探索を防ぎます。実装では隣接リスト表現が大規模グラフで効率的です。
最短経路探索の代表例
重み付きグラフで最短経路を求める場合、代表的な手法として Dijkstra、Bellman–Ford、Floyd–Warshall、Johnson、A* などがあります。
- Dijkstra（ダイクストラ）：非負重みのグラフで単一始点最短経路を求めます。優先度付きキュー（ヒープ）を使い、二分ヒープを用いると計算量は O((V + E) log V)（慣用的に O(E log V）と表現されることもあります）。負の辺がある場合は使用できません。
- Bellman–Ford：負の重みを扱え、負の閉路（負の重量サイクル）を検出できます。単一始点最短経路を求めるアルゴリズムで計算量は O(VE)。負の辺があるネットワークでの安全な選択肢です。
- Floyd–Warshall：全点対最短経路を求める動的計画法。頂点数 V に対して O(V^3) の時間、O(V^2) のメモリで小規模グラフ向け。
- Johnson：多数の始点からの最短経路（全点対）を効率化する手法で、再重み付けと Dijkstra を組み合わせます。疎グラフに有効。
ヒューリスティック探索：A*（エースター）
A* は最短経路探索にヒューリスティック（推定コスト）を導入し、効率よくゴールへ導くアルゴリズムです。各ノード n について f(n) = g(n) + h(n) を評価し、g(n) はスタートから n までの既知最小コスト、h(n) は n からゴールへの推定コストです。
- 最適性：ヒューリスティック h が許容的（admissible）、すなわち実際の最短コストを過小評価しない（過大評価しない）場合、A* は最短経路を返します。さらに h が一貫性（consistent / monotone）であれば、ノードの再展開が不要になり実装が簡潔になります。
- 完全性と計算量：有限な分岐因子と正の辺コストがある場合、解が存在すれば A* は完備です。計算量はヒューリスティックの品質に強く依存し、最良でも Dijkstra 相当、最悪では指数的になります。
- 実装上の注意：オープンセット（優先度キュー）とクローズドセット（訪問済み）を管理し、経路復元のために前任ノード（parent）を保存します。ヒューリスティックは問題依存で設計（例：地図ではユークリッド距離やマンハッタン距離）します。
特殊手法・改善技法
- 双方向探索（Bidirectional Search）：始点側と終点側から同時に探索して中間で合流します。無重みグラフや一様コスト問題で特に有効で、理想的には探索規模を平方根まで削減できます。
- 反復深化 DFS（IDDFS）：深さ制限付き DFS を深さ増加で繰り返し、BFS のような最短路性を保ちつつメモリを節約します。分岐因子が一定で深さが有限な場合に有効です。
- IDA*：A* を反復深化で実装したもので、メモリ使用量を抑えつつヒューリスティック探索の利点を活かします。
- 優先度キューの選択：二分ヒープ、ペアング・ヒープ、フィボナッチ・ヒープなどで性能が変わります。理論的にはフィボナッチヒープが最良ですが、定数因子や実装の複雑さから現実の実装では binary heap（あるいは pairing heap）が多用されます。
- 近似・縮約：巨大グラフではサンプリング、スケッチ、ランドマーク法、ヒエラルキー化（マルチレベルグラフ）などの近似手法が有用です。道路ネットワークの経路検索では事前処理（CH: Contraction Hierarchies、ALT 法など）が非常に効率的です。
実装上の注意点と性能考慮
- 表現の選択：隣接リストは疎グラフ向け、隣接行列は密グラフや定数時間のエッジ存在判定が必要な場合に適します。メモリとアクセスパターンを考慮してください。
- 訪問済み管理：重複探索を避けるために visited（または closed）集合が必須。A* や Dijkstra では距離配列と併用して「より短い経路が発見された場合の再更新」を適切に処理する必要があります。
- 数値精度と無限値：重みの初期化やオーバーフローに注意。無限大表現を一貫して使い、比較条件を厳密に設計します。
- 負の辺：負の辺がある場合は Dijkstra を避け、Bellman–Ford を検討。負の閉路があると最短路が定義されない点に注意します。
- メモリ制約：幅優先や A* はフロンティアが大きくなりがちです。外部メモリや分散処理、近似アルゴリズムの検討が必要です。
- 並列化・分散化：グラフ処理フレームワーク（Pregel、GraphX、Giraph など）を利用すると大規模グラフを分散処理できますが、探索の同期・整合性や通信コストに注意が必要です。
代表的な応用例
- ネットワークルーティング（経路決定、トラフィック工学）
- 地図・ナビゲーション（最短経路、A*）
- ソーシャルネットワーク解析（到達性、中心性、友人推薦）
- 静的解析・依存関係（ビルド順、循環検出、トポロジカルソート）
- ゲーム AI（経路探索、障害回避、戦略探索）
- Web クローリング（接続性探索、ページ発見）
まとめ
グラフ探索アルゴリズムは問題の性質（有向/無向、重みの有無、負の辺の有無、目的：到達可否か最短路か）に合わせて最適な手法を選ぶことが重要です。基本の BFS／DFS に加え、Dijkstra や Bellman–Ford、A* のような最短経路アルゴリズム、双方向探索や反復深化といった改良手法が実務では頻繁に用いられます。実装時はデータ構造、メモリ制約、ヒューリスティックの品質、再探索の扱いなどに注意して設計してください。
参考文献
- 図解析（Wikipedia）
- 幅優先探索（BFS） - Wikipedia
- 深さ優先探索（DFS） - Wikipedia
- ダイクストラ法（Dijkstra） - Wikipedia
- Bellman–Ford 法 - Wikipedia
- A*（Aスター） - Wikipedia
- Stanford CS Lecture Notes — Shortest Paths (英語)
- AIMA: Artificial Intelligence: A Modern Approach（Russell & Norvig） — 探索アルゴリズムの解説（英語）
投稿者プロフィール
