有向無閉路グラフ（DAG）入門：定義・性質・トポロジカルソートとIT実務での応用
エバープレイ編集部有向無閉路グラフ（DAG）とは
有向無閉路グラフ（ゆうこうむへいろグラフ）、一般には英語表記の Directed Acyclic Graph（DAG）と呼ばれる構造は、ノード（頂点）と有向辺（矢印）からなるグラフで、どの頂点から出発しても矢印に沿って辿った際に元の頂点へ戻る「閉路（サイクル）」が存在しないものを指します。すなわち、辺が向きを持ち、循環が一切ない有向グラフがDAGです。
定義と同義表現
形式的には、グラフ G = (V, E) が有向グラフであり、任意の正の長さの経路 v0 → v1 → … → vk（k ≥ 1）について v0 ≠ vk が成り立つとき、G は有向無閉路グラフ（DAG）である。
別表現として、DAG は「部分順序（partial order）」を表現するグラフとも見なせます。有限グラフに対し、到達可能性（到達関係）を順序関係と見れば D 頂点間の到達可能性は反射的・非対称・推移的な関係を与え、部分順序を表します。
用語上は「有向非巡回グラフ」「有向非閉路グラフ」「有向アクyclicグラフ（DAG）」などとも呼ばれます。
基本的性質
DAG にはいくつか重要な数学的・アルゴリズム的性質があります。
トポロジカル順序（topological order）が存在する：DAG の頂点は、有向辺 (u → v) がある場合に常に u を v の前に並べるような線形順序で並べられます。これはグラフがサイクルを含まないことの同値条件です。
到達可能性が部分順序を与える：到達可能性による二項関係は反射的・反対称的・推移的であり、有限 D AG は有限部分順序と同値的に扱えます。
推移閉包（transitive closure）や推移縮約（transitive reduction）といった概念が有用：推移閉包は到達可能性を直接の辺として付け加えたもので、推移縮約はそれらの冗長な辺を取り除いて元の到達関係を保つ最小の辺集合を指します。
主要アルゴリズム
DAG に関する代表的なアルゴリズムとその計算量を概観します。
サイクル検出とトポロジカルソート
Kahn のアルゴリズム：入次数が 0 の頂点をキューに入れて取り出し、その頂点に隣接する辺を削除していくことでトポロジカル順序を得ます。もしすべての頂点を処理できない（残りに入次数 0 の頂点がない）場合はサイクルが存在します。計算量は隣接リスト表現で O(V + E) です。
DFS による方法：深さ優先探索（DFS）を行い、訪問完了（ポストオーダー）した頂点を逆順に並べることでトポロジカル順序が得られます。探索中に「活性化中（探索途中）の頂点へ戻る辺」が見つかればサイクルの存在が確認できます。計算量は O(V + E) です。
最短経路・最長経路（重み付き辺を含む場合）
DAG に対しては、重み付き辺があってもトポロジカル順序に従う一回の巡回で単一始点最短／最長経路を計算できます。始点からトポロジカル順に緩和（relax）していくことで実行でき、計算量は O(V + E)（辺の数に比例）です。
一般グラフでの最長経路問題は NP-ハードですが、DAG では多項式時間で解けるという重要な特性があります。
推移閉包・縮約
推移閉包はワーシャル–フロイドなどのアルゴリズムでも得られますが、DAG の場合はトポロジカル順序に基づく動的計画法で効率的に構築できます。
推移縮約（transitive reduction）は部分順序を最小限の辺で表すもので、DAG に対して一意に定まります（有限グラフの場合）。実用上、依存関係の可視化で冗長な辺を削るのに有用です。
データ構造と実装上の注意
表現：頂点数が大きく疎なグラフなら隣接リストが一般的。密なグラフや行列演算が必要な場合は隣接行列を使います。
増分更新：大規模システムでは依存関係が逐次追加されることが多く、追加辺によってサイクルが生じるかを効率的に検出する（例：部分順序に新しい制約を追加する際の整合性チェック）が重要です。
可視化：トポロジカルレイアウトや層別レイアウト（層ごとに深さを割り当てる）で分かりやすく描画できますが、推移閉包を描画すると辺が爆発的に増えるため、推移縮約で簡潔にすることが多いです。
代表的な実用例（IT分野での応用）
タスクスケジューリング：ジョブの先行関係を DAG で表し、トポロジカル順に実行することで依存を満たします。並列実行の可能性（独立な頂点）を発見しやすい構造です。
ビルドシステム（Make、Bazel、Ninja など）：ソースファイルや生成物の依存関係を DAG として管理。再ビルド対象の決定や並列ビルドに利用されます。
ワークフロー管理（Airflow、Luigi 等）：DAG をタスクの流れとして表現し、スケジューラがトポロジカル順でタスクを実行します（Airflow はワークフローを明示的に DAG として扱います）。
バージョン管理（Git）：コミットは親コミットを指すポインタを持ち、親方向に向かう有向辺で表される DAG 構造（実装的には有向非巡回グラフ）です。ブランチやマージを含めても基本的に循環は生じません。
ベイジアンネットワーク：確率的因果関係を表すときに DAG が使われます。因果方向と条件付き独立性の表現に重要です（有向グラフだがサイクルがあると因果解釈が困難）。
プロジェクト管理（クリティカルパス法：CPM）：工程間の先行関係を DAG として表し、最長経路解析によりプロジェクト全体の所要時間や余裕（フロート）が求められます。
分散台帳・ブロックチェーンの一部応用：従来のブロックチェーンは連鎖（チェーン）ですが、IOTA の Tangle や DAG を用いる分散台帳はトランザクション間の承認構造を DAG で表現します（実装と安全性は設計に依存します）。
設計上の注意点・落とし穴
依存関係の循環：依存グラフにサイクルが入るとトポロジカル順序が存在せず、タスクやビルドの実行が停止します。設計段階で循環の発生を防ぐルールやチェックを導入することが重要です。
スケーラビリティ：巨大な DAG（ノード数・辺数が非常に大きい）ではトラバースや可視化が重くなるため、サブグラフ分割や階層化、インデックス（到達可能性クエリ用の前処理）を検討します。
冗長な辺：推移閉包をそのまま持つと辺の数が増え、操作が遅くなることがあります。可視化や一部操作では推移縮約を使うと助かります。
不変条件の検証：運用中に辺を追加・削除する API を提供する場合、整合性チェック（サイクル検出、依存満足性）と効率的な実装が必要です。
実務でのヒント
トポロジカルソートは単に「依存関係の順序」を得るだけでなく、並列化の候補（同じレイヤのノード）を見つけるのに使える。
重み付きタスク（実行時間など）がある場合、最長経路問題を使ってクリティカルパスを求め、ボトルネックを特定する。
大規模データパイプラインでは、DAG の各ノードにメタデータ（最終実行結果、成功/失敗、タイムスタンプ）を持たせると運用とデバッグが容易になる。
まとめ
DAG（有向無閉路グラフ）は、依存関係や因果関係、処理の順序性を表現する上で極めて重要なデータ構造です。トポロジカルソートや DFS によるサイクル検出、トポロジカル順を用いた最短／最長経路解析といった効率的なアルゴリズムが存在するため、一般的なグラフ問題で難解なものが DAG では多項式時間で解けるケースが多いのが特徴です。IT の実務ではビルド、スケジューラ、ワークフロー管理、確率モデルなど幅広い応用があり、正しい設計と運用ルールがあれば堅牢でスケーラブルなシステムの基盤となります。
参考文献
- Directed acyclic graph — Wikipedia
- Topological sorting — Wikipedia
- Transitive reduction — Wikipedia
- Kahn's algorithm — Wikipedia (Topological sorting の節)
- Apache Airflow — Workflow management platform
- Pro Git — Git Internals (コミットオブジェクトの説明)
- Critical path method — Wikipedia
- Tangle (IOTA) — Wikipedia（DAG を用いる分散台帳の一例）
投稿者プロフィール
