グラフ探索入門：BFS/DFSから最短経路アルゴリズムと実務応用まで徹底解説
エバープレイ編集部グラフ探索とは — 基本概念とITでの重要性
グラフ探索（グラフ探査、graph search）は、ノード（頂点）とそれらを結ぶエッジ（辺）で表現されるグラフ構造を順に辿り、特定の頂点の到達可能性や経路、構造的な性質（連結成分・サイクルの有無など）を調べる一連の手法群を指します。IT分野ではネットワーク解析、経路探索、依存関係解析、ゲームの経路探索、コンパイラの最適化など多岐にわたって用いられ、アルゴリズム設計の基本中の基本です。
グラフの基本と表現方法
グラフは大きく有向グラフ（方向がある）と無向グラフ（方向なし）に分かれます。辺に重み（コスト）を持つ重み付きグラフも重要です。プログラムで扱う際の代表的な表現は以下の通りです。
- 隣接リスト（adjacency list）: 各頂点に隣接する頂点のリストを持つ。疎なグラフに適し、メモリ効率が良い。BFS/DFSの計算量は O(V + E)（V: 頂点数、E: 辺数）。
- 隣接行列（adjacency matrix）: V×V 行列で辺の有無（または重み）を管理。密なグラフや定数時間での辺存在チェックに有利。計算量は O(V^2)。
- 辺リスト（edge list）: 全辺を列挙。アルゴリズム（例：クラスカル法）で重みソートを行うときに使う。
代表的な探索アルゴリズム
探索の目的やグラフの性質によって適切なアルゴリズムは変わります。ここでは基礎かつ頻出のものを解説します。
BFS（幅優先探索）
幅優先探索は、ある始点から距離（辺の数）ごとに層状に幅広く探索していきます。キューを用いて実装され、到達可能性の判定や「最短経路（辺数ベース）」の計算に使われます。複雑度は隣接リスト実装で O(V + E) です。
DFS（深さ優先探索）
深さ優先探索は、可能な限り深く下りていき、行き止まりになれば一つ前に戻って別の経路を試す方法です。再帰または明示的なスタックで実装できます。到達性チェック、トポロジカルソート、サイクル検出、連結成分の分離（無向グラフ）などに使われます。複雑度は O(V + E) です。注意点として、経路が最短になるとは限りません。
双方向探索（Bidirectional Search）
探索空間が大きく、始点と終点が分かっている場合、始点側と終点側から同時に探索して衝突点を探す手法です。適切に使えば探索量を大幅に削減できますが、実装上の同期やメモリ管理が少し複雑になります。
最短経路問題と代表的アルゴリズム
「最短経路」は重み付きグラフにおける代表的な課題です。重みの符号やグラフの大きさにより適切なアルゴリズムが異なります。
Dijkstra（ダイクストラ）
非負の重みがあるグラフの単一始点最短経路を求める代表アルゴリズムです。優先度付きキュー（ヒープ）を用いると計算量は O(E log V)（実装依存）程度になります。負の辺があると正しく動作しません。
Bellman–Ford（ベルマン–フォード）
負の辺を許す単一始点最短経路アルゴリズム。負のサイクルがある場合は検出できます。計算量は O(VE) とやや重めですが、負の重みを扱う必要がある場面で有用です。
A*（エースター）
ヒューリスティック（推定コスト）を用いることで実際の探索量を削減する方法です。f(n) = g(n) + h(n)（g: 始点からの実コスト、h: 目的地までの推定コスト）を評価して優先度キューで展開します。h が「過小評価（admissible）」であれば最短経路が保証されます。地図の経路探索やゲームのAIで広く使われます。
その他の関連アルゴリズムと解析
- トポロジカルソート：有向非巡回グラフ（DAG）における線形順序の決定。依存関係解決に利用。
- 強連結成分（SCC）：Tarjan法やKosaraju法で O(V + E) 時間に求められる。有向グラフのクラスター解析に重要。
- 最小全域木（MST）：クラスカル法、プリム法が代表。ネットワーク設計やクラスタリングで用いられる。
- サイクル検出：DFS を使った白/灰/黒マーカーや、集合（Union-Find：クラスカルで利用）で検出可能。
計算量と実装上の注意点
代表的な探索は隣接リストを用いると O(V + E) が多く、これはグラフ全体を一度(あるいは定数回)辿ることに対応します。隣接行列だと O(V^2) になる点に注意してください。重み付き最短経路では、Dijkstra（非負重み）やBellman-Ford（負重み可）、A*（ヒューリスティック次第）を適切に選ぶ必要があります。
実装の実務上の注意点：
- 訪問済みフラグ（visited）を忘れると無限ループや重複処理、計算量爆発を招く。
- 再帰実装は簡潔だが、深いグラフではスタックオーバーフローに注意。ループベースの実装や明示的スタックを検討する。
- ヒープや優先度付きキューの減少キー操作（decrease-key）は実装方法で性能に影響。ライブラリ実装を利用するか、複数挿入で代用するテクニックがある。
- A* のヒューリスティックは「許容的（admissible）」かつできれば「整合性（consistent）」を満たすと理論保証が得られる。過大評価すると最短解が失われる。
応用例（IT・実務での使いどころ）
- ネットワークルーティング（経路決定、トラフィック最適化）
- ソーシャルネットワーク分析（到達性、コミュニティ検出、中心性指標）
- 地図・ナビゲーション（A* を用いた最短経路探索）
- 依存関係解析（ビルドシステム、パッケージ管理のトポロジカルソートや循環検出）
- ゲームAI（経路探索や行動計画）
- コンパイラ（制御フロー解析、最適化）
よくある誤解とチェックポイント
いくつかの典型的な誤解とその確認方法を示します。
- 「DFS は常に最短経路を返す」— これは誤り。無重みグラフでも最短（辺数）を保証するのは BFS です。
- 「Dijkstra は負の重みでもOK」— これは誤り。負の辺がある場合は Bellman–Ford を検討する必要があります。
- メモリ計算の見落とし — 大規模グラフでは辺数が膨大になり得るため、隣接リストや外部記憶による処理、ストリーミングアルゴリズムを検討する。
実践的なTips
- 探索のたびにデータ構造を初期化するコストを考慮する。複数クエリがある場合は前計算（距離行列、経路木）を検討する。
- 重みが全て等しい（または単位）なら BFS、負の重みがあるなら Bellman–Ford、非負重みかつ大規模なら効率的ヒープ実装の Dijkstra を選ぶ。
- メモリ制約が厳しい場合は、探索空間を絞る（ヒューリスティック、プルーニング）や外部メモリアルゴリズムの利用を検討する。
まとめ
グラフ探索はITの多くの課題を解くための中核技術です。基本である BFS と DFS を押さえた上で、目的（到達性、最短経路、構造解析）に応じて Dijkstra、Bellman–Ford、A*、Tarjan 等のアルゴリズムを使い分けることが重要です。実装ではデータ構造選択やメモリ・計算量の見積もり、ヒューリスティックの妥当性など現実的な考慮が不可欠です。
参考文献
- アルゴリズム（Wikipedia 日本語）
- 幅優先探索（BFS） - Wikipedia
- 深さ優先探索（DFS） - Wikipedia
- ダイクストラ法 - Wikipedia
- ベルマン–フォード法 - Wikipedia
- A*（エースター） - Wikipedia
- 最小全域木（MST） - Wikipedia
- 参考書（アルゴリズム入門や教科書）：Cormen, Leiserson, Rivest, Stein（CLRS） や各種講義ノート（英語・日本語）
投稿者プロフィール
