有向グラフ入門：定義・表現・主要アルゴリズム（トポロジカルソート・SCC・最短経路）と実装上の注意点
エバープレイ編集部有向グラフとは — 概要
有向グラフ（ゆうこうグラフ, directed graph または digraph）は、頂点（ノード）とそれらを結ぶ辺（エッジ）から構成されるグラフの一種で、各辺に向き（方向性）が定められているものを指します。辺は順序対 (u, v) として表され、「u から v へ向かう」ことを意味します。向きのあることで、関係や操作の非対称性（例：依存関係、リンク、信号の流れなど）を自然に表現できます。
形式的定義と基本用語
有向グラフ G は通常 G = (V, E) と書かれ、V は頂点集合、E は有向辺の集合（E ⊆ V × V）です。基本用語を整理します：
- 始点と終点：辺 (u, v) の始点は u、終点は v。
- 出次数（outdegree）：ある頂点から出る辺の本数。
- 入次数（indegree）：ある頂点に入る辺の本数。
- 有向パス：v0 → v1 → ... → vk のように各隣接が有向辺でつながる列。
- 有向閉路（サイクル）：始点と終点が同じで長さ ≥ 1 の有向パス。
- simple directed graph：自己ループや重複辺を許さない有向グラフ。ループや多重辺がある場合は有向多重グラフと呼ばれる。
表現方法と計算量
有向グラフは主に二つの方法で表現されます。選択は用途や計算の種類に依存します。
- 隣接リスト（Adjacency List）：各頂点について、そこから出る隣接頂点のリストを保持。メモリは O(V + E)。辺の列挙やグラフ探索（DFS/BFS）が効率的。典型的な探索コストは O(V + E)。
- 隣接行列（Adjacency Matrix）：V×V の二次元配列で、行 u、列 v が 1 なら辺 (u, v) が存在。メモリは O(V^2)。辺の存在確認は O(1)。しかし疎グラフでは非効率。
アルゴリズムの時間計算量例：
- 深さ優先探索（DFS）・幅優先探索（BFS）：O(V + E)
- トポロジカルソート（DAG の場合）：O(V + E)
- 強連結成分分解（Kosaraju や Tarjan）：O(V + E)
- 単一始点最短経路（非負重み、Dijkstra）：実装により異なるがヒープを用いると O((V + E) log V)（多くの場合 O(E log V）と表現）
- 単一始点最短経路（負の重み許容、Bellman–Ford）：O(VE)
- 全点対最短経路（Floyd–Warshall）：O(V^3)
- 推移閉包（transitive closure, Warshall）：O(V^3)（行列ベース）
重要な性質と概念
有向グラフならではの性質や、解析で頻出する概念を説明します。
- 強連結（Strongly Connected）：任意の u, v について u から v、かつ v から u へのパスが存在する場合、グラフは強連結。強連結成分（SCC）はグラフを分割した極大の強連結部分グラフ。
- 弱連結（Weakly Connected）：辺の向きを無視したとき連結であれば弱連結と呼ぶ。
- 有向非巡回グラフ（Directed Acyclic Graph, DAG）：サイクルを含まない有向グラフ。DAG はトポロジカル順序（タスクの依存解決など）を持ち、部分順序を表現するのに頻用される。
- 縮約グラフ（Condensation Graph）：各 SCC を一つのノードに縮約すると得られるグラフで、これは常に DAG になる。
- オイラー路・オイラー閉路：有向グラフのオイラー閉路（すべての辺をちょうど一度通って始点に戻る巡回）は、各頂点の入次数と出次数が等しいこと、かつ適切な連結性（非零辺を含む部分で強連結かその弱版）が必要。
- ハミルトン路：頂点を一度ずつ訪れる経路を求める問題は一般に NP-完全。
代表的なアルゴリズムと用途
有向グラフ解析でよく使われるアルゴリズムとその利用ケースを示します。
- 深さ優先探索（DFS）・幅優先探索（BFS）：到達可能性の判定、探索木の構築、サイクル検出などの基礎。
- トポロジカルソート：DAG に対して依存関係の線形化（ビルド順、タスクスケジューリング、コンパイラの最適化順序など）。DFS ベースや入次数管理（Kahn のアルゴリズム）で O(V + E)。
- 強連結成分分解（Kosaraju、Tarjan）：モジュール分解、縮約グラフ作成。どちらも O(V + E)。
- 最短経路アルゴリズム：Dijkstra（非負重み）、Bellman–Ford（負の重みも可）、Floyd–Warshall（全点対）。交通網、ルーティング、コスト最小化など。
- 推移閉包（Transitive closure）：到達可能性を一括で落とし込む際に使用（アクセス権の伝播解析など）。Warshall アルゴリズムなど。
- PageRank や中心性計測：Web のハイパーリンクやソーシャルグラフは有向グラフで表現され、PageRank は遷移確率行列の固有値問題（反復法）に基づく。
実用例（ケーススタディ）
有向グラフは多くの実世界問題をモデル化します。主な例：
- ウェブグラフ：ウェブページを頂点、ハイパーリンクを有向辺として検索エンジンのランキング（PageRank）やクロール戦略に利用。
- 依存関係管理：ソフトウェアパッケージの依存やビルド順（コンパイル順）は DAG で表現し、トポロジカルソートで順序を決定。
- 制御フローグラフ（コンパイラ）：実行の流れを有向グラフで表し、最適化や到達分析に SCC や支配木を使う。
- 交通・物流ネットワーク：道路や航路の一方通行制約を表現。最短経路や最小コストフロー問題が中心。
- ワークフローとスケジューリング：業務プロセスの依存関係管理や並列化。
実装上の注意点・落とし穴
実際に有向グラフを扱う際の注意点を列挙します：
- グラフのサイズと表現：頂点数が多い疎グラフでは隣接リストが必須。隣接行列はメモリを食い過ぎる。
- 重み付き辺の符号：負の重みがある場合は Dijkstra を使ってはいけない（誤った結果）。Bellman–Ford を検討する。
- 循環の検出：依存関係が循環するとトポロジカル順序が存在しない。CI やパッケージ管理では事前に検出してエラーにする必要あり。
- 浮動小数点と PageRank：ページランク等で確率遷移行列を扱う際は正規化と収束判断（絶対誤差や相対誤差）に注意。
- 連結性の扱い：有向グラフの「連結」は強連結／弱連結という区別があり、目的に応じて正しい概念を使うこと。
拡張トピック（高度な話題）
より深い解析や実装で役立つトピックを簡単に紹介します：
- 縮約と DAG 化：大規模グラフを SCC ごとに縮約すると DAG になり、上位レベルの解析や最適化が容易になる。
- 動的グラフ：辺や頂点の追加・削除が頻繁に起きる場合は、完全再計算よりも動的アルゴリズム（動的最短路や incremental SCC）を検討。
- 確率遷移行列と固有値解析：PageRank は確率遷移行列の固有ベクトルを求める問題に帰着し、線形代数ライブラリや疎行列処理が重要。
- 並列化・分散処理：巨大グラフ（ウェブスケール）では分散フレームワーク（Pregel, GraphX, Gelly など）を用いて処理する。
まとめ
有向グラフは、向きのある関係を自然にモデル化できるため、IT 分野では欠かせないデータ構造です。表現方法（隣接リスト／行列）の選択やアルゴリズム（DFS/BFS、トポロジカルソート、SCC、最短経路など）の適用を正しく行えば、依存解決、最短経路、ランキング、ワークフロー管理など多様な実問題を効率よく解決できます。一方で負の重みや循環、巨大データの取り扱いなどの注意点があり、用途に応じたアルゴリズム設計や実装上の工夫が求められます。
参考文献
- 有向グラフ - Wikipedia（日本語）
- Directed graph - Wikipedia (英語)
- トポロジカルソート - Wikipedia（日本語）
- Topological sorting - Wikipedia (英語)
- 強連結成分 - Wikipedia（日本語）
- Strongly connected component - Wikipedia (英語)
- Dijkstra's algorithm - Wikipedia (英語)
- Bellman–Ford algorithm - Wikipedia (英語)
- Floyd–Warshall algorithm - Wikipedia (英語)
- PageRank - Wikipedia (英語)
- Cormen, Leiserson, Rivest & Stein: Introduction to Algorithms（書籍）
投稿者プロフィール
