有向非巡回グラフ（DAG）完全ガイド：定義・主要アルゴリズム・IT応用と設計上の注意点
エバープレイ編集部有向非巡回グラフ（DAG）とは — 概念と定義
有向非巡回グラフ（Directed Acyclic Graph、略して DAG）は、頂点（ノード）と有向辺（エッジ）から構成されるグラフで、どの頂点から出発しても同じ頂点に戻ってくるような「有向の閉路（サイクル）」が存在しないグラフを指します。つまり、辺は向きを持ち、グラフ内に向き付きのサイクルが存在しない点が特徴です。
数学的性質と基本概念
DAG は部分的順序（partial order）を表現でき、しばしば「因果関係」や「依存関係」をモデル化する際に用いられます。主な性質は次の通りです。
- サイクルが存在しない：任意の頂点 v に対して、v から出発して v に戻る有向パスが存在しない。
- トポロジカル順序の存在：DAG には少なくとも 1 つのトポロジカル（トポロジカルソート）順序が存在する。これは、全ての有向辺 u → v に対して u が v の前に並ぶ線形順序である。
- 遅延（レベル）構造：根（入次数が 0 の頂点）から終端（出次数が 0 の頂点）へと流れる「層」を意識できる。
表現方法
DAG は以下のような一般的なデータ構造で表現されます。
- 隣接リスト（Adjacency List）：各頂点ごとに出隣接頂点のリストを持つ。疎グラフで効率的。
- 隣接行列（Adjacency Matrix）：頂点数が小さい場合は高速な隣接判定が可能。密なグラフには向く。
- エッジリスト：単に辺の集合を持つ表現。並列処理やストリーム処理で扱うことがある。
基本アルゴリズムと計算量
DAG に対する代表的なアルゴリズムとその計算量（n を頂点数、m を辺数とする）を示します。
- トポロジカルソート（Kahn のアルゴリズムおよび DFS ベース）：O(n + m)。DAG で頂点を依存関係に従って線形に並べる。
- サイクル検出（DFS による訪問色法など）：O(n + m)。到達探索中に「グレー→グレー」の辺が見つかればサイクルがある。
- 最長経路（重み付き、負の辺を含まない場合）：DAG ではトポロジカル順序を利用した DP で O(n + m)。一般グラフの最長経路は NP-hard（負の閉路など複雑な場合）。
- 最短経路（辺重みがある場合）：負重辺がないとき、トポロジカル順序に基づく DP で O(n + m)。
代表的な適用分野（IT）
DAG は多くの IT 分野で基礎的なモデルとして使われます。以下に主要な適用例を挙げ、それぞれのポイントを説明します。
1) ビルドシステムと依存解決
Make や Bazel、Ninja といったビルドツールは、ソースファイルやターゲット間の依存関係を DAG として扱います。トポロジカルソートにより、どの順番でコンパイル／リンクすべきかを決定します。依存にサイクルがあると再帰的にビルドできないため、サイクル検出が必須です。
2) ワークフロー／データパイプライン（Airflow、Luigi、Spark）
ワークフローエンジン（例：Apache Airflow）は DAG をタスクの依存グラフとして扱います。DAG に従ってタスクをスケジュール・並列実行し、失敗時のリトライやスキップ、境界条件を管理します。Apache Spark ではジョブ内部での演算依存を DAG として解析し、最適化と実行計画の生成に利用します。
3) バージョン管理（Git のコミットグラフ）
Git のコミット履歴は「各コミットが親コミットを指す有向辺」を持つグラフとなり、サイクルは存在しません（コミットは過去の状態を参照するため）。したがって Git の内部構造は DAG に該当します。マージやブランチは DAG 上の異なるパスと考えられます。
4) 分散台帳およびブロックチェーンの代替構造
伝統的なブロックチェーンはチェーン（線形）構造ですが、いくつかの分散台帳プロジェクトは DAG を用いてスループットや最終確定性を改善しようとしています。例として IOTA（Tangle）や Nano（Block Lattice）などが挙げられます。ただし、DAG ベースの台帳設計はトラストモデルや双方向競合管理、最終性の確保などで独自の課題（例：二重支出の防止や一致性の達成）を抱えます。
5) 確率グラフィカルモデル（ベイジアンネットワーク）
ベイジアンネットワークは確率変数間の因果・条件付き独立性を表すモデルで、グラフは DAG で表現されます。DAG によって変数の因果順序や推論の順序が定まり、効率的な推論アルゴリズム（変数排除、メッセージパッシングなど）が適用されます。
6) コンパイラと最適化（式木・依存解析）
コンパイラの内部では、式の依存関係や命令の依存性を DAG として表現し、命令選択や並列化（アウトオブオーダー実行、スーパ・スカラー最適化）に利用します。データフロー解析や最適化フェーズは DAG に対する変換の連続とみなせます。
アルゴリズム詳細（トポロジカルソートとサイクル検出）
代表的アルゴリズムを簡潔に説明します。
- Kahn のアルゴリズム：入次数が 0 の頂点をキューに入れ、取り出して出辺を削除（入次数を減らす）していく。すべての頂点を処理できれば DAG、途中でキューが空で未処理頂点が残るならサイクルあり。計算量は O(n + m)。
- DFS ベースのアルゴリズム：訪問状態を未訪問／訪問中（グレー）／訪問済み（ブラック）に分類し、訪問中の頂点へ向かう辺（グレーへの後退辺）が発見されればサイクルがある。これを応用して DFS によるトポロジカルソート（終了時刻の逆順）も可能。
- 最長経路（DAG）：トポロジカル順序で順に DP を行い、各頂点に到達する最大コストを更新する。一般グラフでの最長経路問題と比べて DAG では多項式時間で解ける点が大きい。
設計上の注意点と落とし穴
DAG を利用する際の実務的な注意点を挙げます。
- サイクルの発生と検出：依存関係を動的に変更するシステムでは、意図しないサイクルが発生しやすい。CI/CD やビルド設定、ワークフロー定義の変更時はサイクル検出を自動化することが重要です。
- 可視化とデバッグ：複雑な DAG は可視化しないと依存関係やボトルネックの特定が難しい。グラフ描画ツールや階層表示を導入しましょう。
- スケーリングと並列性：DAG の並列実行は依存が許す範囲で有効だが、入次数・出次数の偏りや一部ノードの重い処理がボトルネックになり得る（クリティカルパス）。
- 永続化と検証：分散環境で DAG を共有する場合、矛盾や競合の解消ルール（例：最終的な合意アルゴリズムやコンフリクト解決戦略）を明確にしておく必要がある。
- セキュリティ（台帳系の応用）：DAG ベースの台帳は従来のブロックチェーンと異なる脅威モデルを持つ。攻撃耐性（例：二重支出攻撃、スパム攻撃）やガバナンス設計に注意が必要。
実践的パターンとベストプラクティス
DAG を使う場面における実務的なヒントです。
- 明示的な依存を小さく保つ：モジュールやタスクは可能な限り独立に設計して、DAG の分岐と結合をシンプルに保ちましょう。
- トポロジカル順序をキャッシュ：何度も同じ DAG を走査するなら、トポロジカル順序をキャッシュして再利用すると高速化できる。
- 階層化：大規模 DAG はサブDAG に分割して管理し、再利用可能なサブワークフローに抽象化する。
- 障害時のリカバリ設計：部分失敗や再実行に備え、タスクを冪等（idempotent）に設計する、チェックポイントを置くなどの工夫を行う。
まとめ
有向非巡回グラフ（DAG）は、依存関係や因果関係を表現する際に極めて有用なデータ構造です。トポロジカルソートや DP による最長／最短経路計算など効率的なアルゴリズムが存在し、多様な IT 分野（ビルドシステム、ワークフロー、分散台帳、ベイジアンネットワーク、コンパイラ最適化など）で広く使われています。一方で、サイクル検出・可視化・スケーリング・セキュリティといった実務上の課題もあり、設計・運用における配慮が必要です。
参考文献
- 有向非巡回グラフ - Wikipedia（日本語）
- Directed acyclic graph - Wikipedia (English)
- Topological sorting - Wikipedia
- Apache Airflow — DAGs (公式ドキュメント)
- Apache Spark — スケジューリングと DAG（公式ドキュメント）
- Pro Git — Git の内部構造（日本語訳）
- IOTA（Tangle）公式サイト
- Nano — Block Lattice（公式ドキュメント）
投稿者プロフィール
