方向付きグラフ（有向グラフ）完全ガイド：定義・性質・アルゴリズム・応用
エバープレイ編集部はじめに — 方向付きグラフとは何か
方向付きグラフ（有向グラフ）は、頂点の集合 V と有向辺（向きのある辺）の集合 E からなるグラフ G=(V,E) を指します。各辺は順序対 (u,v) の形で表され、u から v への方向性を持ちます。情報の流れ、依存関係、Web のリンク、ソーシャルネットワークの「フォロー」関係など、向きの意味を持つ関係を自然にモデリングできます。
基本的な表記と性質
有向グラフでは以下の基本概念が重要です。
- 始点・終点: 辺 (u,v) は u を始点（出発点）、v を終点（到達点）とする。
- 入次数・出次数: 頂点 v の入次数 indeg(v) は v に入ってくる辺の数、出次数 outdeg(v) は v から出る辺の数。
- パス（道）とサイクル: 有向パスは辺の向きに従って連続する頂点列。始点と終点が一致する正の長さの有向パスは有向サイクル（向きつきの循環）となる。
- 強連結性と弱連結性: 任意の u, v に対して u→v かつ v→u へ到達可能ならば強連結。辺の向きを無視したときに連結であれば弱連結。
データ構造としての表現
有向グラフを表現する主要な方法は次のとおりです。
- 隣接リスト: 各頂点に出ていく辺のリストを持つ。スパースグラフ（E≪V^2）に対してメモリ効率・走査効率ともに優れる。探索やアルゴリズムの多くは O(V+E) の時間で動作する。
- 隣接行列: V×V の行列 A で、A[u][v]=1（重み付きなら重み）とする。一定のインデックスアクセスが O(1) で可能だが、メモリは O(V^2)。行列の冪乗やスペクトル解析に向く。
- 辺リスト: 単純に全辺の列挙。アルゴリズムや入出力に便利。
到達性と推移閉包
頂点 u から v に到達可能か（到達性）はグラフ理論・アルゴリズムの中核問題です。深さ優先探索（DFS）や幅優先探索（BFS）で単一始点からの到達集合を O(V+E) で求められます。全頂点対の到達性（推移閉包）は、各頂点から BFS/DFS を実行する方法で O(V(V+E))、あるいは Warshall（Floyd–Warshall の一部）による行列演算で O(V^3) の時間で得られます。
強連結成分（SCC）と縮約グラフ
有向グラフは強連結成分（強連結な頂点集合）に分解できます。代表的なアルゴリズムは次の通りです。
- Kosaraju のアルゴリズム: 2 回の DFS（1 回は逆向きグラフ上）で O(V+E)。
- Tarjan のアルゴリズム: 1 回の DFS で低リンク値を用い O(V+E)。実装上のスタック管理が必要。
全ての強連結成分を一つの頂点に縮約すると、縮約グラフは必ず有向非循環グラフ（DAG）になります。これを用いると高レベルの依存関係解析が容易になります。
有向非循環グラフ（DAG）とトポロジカルソート
DAG（有向非巡回グラフ）はサイクルを含まない有向グラフで、依存関係やビルド順序の表現に頻出します。トポロジカルソートは、すべての辺 (u,v) に対して u が v より前に来るような頂点順序を与えます。実行法は主に次の 2 種類です。
- Kahn のアルゴリズム: 常に入次数 0 の頂点を取り出して順序を構築する。時間 O(V+E)。サイクルがあると処理残りが発生する。
- DFS ベース: DFS の帰りがけ順序を逆にする。こちらも O(V+E)。
最短経路問題（有向グラフ上）
有向グラフ上の最短経路問題はエッジの重みの性質によって解法が異なります。
- 非負重み: Dijkstra アルゴリズムが適用でき、ヒープ（優先度付きキュー）を使うと O((V+E) log V)（通常は O(E log V））の計算量。
- 負辺を含むが負閉路なし: Bellman–Ford アルゴリズムで O(VE)。単一始点最短路を保証。
- 全頂点対の最短路: Floyd–Warshall で O(V^3)。行列演算的アプローチ。
- トポロジカル順序を用いる: DAG の場合、トポロジカル順序に沿って単一始点最短路を O(V+E) で計算可。
行列・スペクトル的観点
有向グラフの隣接行列 A は非対称であることが多く、固有値・固有ベクトルは複素数になる場合があります。PageRank のような確率遷移行列を用いる手法は、行列の固有ベクトル（定常分布）に基づく重要度評価を行います。隣接行列の冪 A^k の (u,v) 成分は長さ k の有向歩の数を与えるため、ウォークベースの解析やランダムウォークの振る舞いの理解に役立ちます。
アルゴリズムの計算量と実装上の注意
実運用での選択基準は主にグラフの密度と操作内容です。スパースグラフでは隣接リストと O(V+E) のアルゴリズムが中心。頻繁に辺の有無チェックや行列演算が必要な場合は隣接行列を選ぶことがあります。メモリ、並列化、キャッシュ効率、I/O（外部メモリ）なども設計上重要です。
ランダムグラフモデルと生成モデル
有向グラフの生成モデルには、エルデシュ–レーニー型の有向版（各順序対 (u,v) を独立に確率 p で付与）や、有向の優先的アタッチメント（優先度を入出力に分ける）などがあります。これらのモデルは大規模ネットワークの統計的性質やスケーラビリティの評価に使われます。
実世界での応用例
有向グラフは多くの分野で用いられます。
- ソーシャルメディア: フォロー／フォロワー関係（非対称）
- Web グラフ: ページ間のリンク（PageRank の応用）
- コンパイラ・ソフトウェア工学: 制御フローグラフ／呼び出しグラフ、依存関係解析
- タスクスケジューリング・ワークフロー: DAG による依存解決と順序決定
- 道路交通ネットワーク: 一方通行や向き依存の重み付き辺
- 知識グラフ・因果モデル: 有向エッジで因果方向を表現
応用上の実務的アドバイス
実装と運用でよく遭遇するポイントは以下の通りです。
- 大規模グラフではメモリ効率が最優先。圧縮隣接リストや外部メモリアルゴリズムを検討する。
- 強連結成分の縮約により問題を低次元化できる場合が多い。ループや相互依存を除去してから解析すると効率的。
- DAG ならばトポロジカルソートを活用して動的計画法や並列化を行うと高速化しやすい。
- 負辺や負閉路の有無は早期にチェックする。Bellman–Ford は負閉路検出にも用いられる。
- 確率やランダムウォークを扱う場合は、行列正規化やランク逸脱（dangling nodes）の扱いに注意する（PageRank の実装課題）。
高度なトピック（概観）
より高度な研究・実践分野としては、動的有向グラフ（エッジの追加・削除が頻繁に発生する環境での増分アルゴリズム）、大規模並列分散処理（GraphX、Pregel 系フレームワーク）、確率的・時間依存グラフ、属性付き有向グラフの機械学習（GNN の有向拡張）などが挙げられます。また、スペクトル理論や行列分解はコミュニティ検出やリンク予測に応用されます。
まとめ
方向付きグラフ（有向グラフ）は向きを持つ関係を表現する強力な抽象化で、アルゴリズムやデータ構造の選定が応用の効率性を左右します。到達性、強連結成分、DAG とトポロジカルソート、最短経路アルゴリズム、行列的手法といった基本技術を押さえることで、依存解析やネットワーク解析、最適化問題など幅広い課題に対処できます。実装ではグラフのサイズ・密度・更新頻度を踏まえた表現選択とアルゴリズム選択が重要です。
参考文献
有向グラフ - Wikipedia（日本語）
Directed graph - Wikipedia (EN)
強連結成分 - Wikipedia（日本語）
Topological sorting - Wikipedia (EN)
Tarjan's algorithm - Wikipedia (EN)
Kosaraju's algorithm - Wikipedia (EN)
Dijkstra's algorithm - Wikipedia (EN)
Bellman–Ford algorithm - Wikipedia (EN)
Floyd–Warshall algorithm - Wikipedia (EN)
PageRank - Wikipedia (EN)
投稿者プロフィール
