有向非巡回グラフ（DAG）徹底解説：性質・トポロジカルソート・アルゴリズム・実世界応用
エバープレイ編集部有向非巡回ネットワーク（Directed Acyclic Network）とは
有向非巡回ネットワーク（Directed Acyclic Network）は、数学・計算機科学では一般に「有向非巡回グラフ（DAG: Directed Acyclic Graph）」と呼ばれる構造を指します。これは頂点（ノード）と有向辺（矢印）からなるグラフで、どの頂点から出発して辺に沿って移動しても同じ頂点に戻ってくるような有向の閉路（サイクル）が存在しないものです。つまり、矢印の方向に従って辿ると必ず進行方向に「順序」が決まるネットワーク構造です。
基本的な性質
- 非巡回性: 有向閉路（v1 → v2 → ... → v1）が存在しない。これがDAGの定義そのものです。
- 部分順序との対応: DAGは到達可能性に基づく部分順序（partial order）を自然に表現します。頂点間の到達可能性（uからvへパスが存在するか）によって順序関係を考えることができます。
- トポロジカル順序（拓撲ソート）: DAG上の頂点は、すべての有向辺 (u→v) に対して u が v より前に現れる線形順序（トポロジカル順序）に並べることができます。この並び方は複数存在する場合があり、数えることは一般に困難（#P困難）です。
- トランジティブ閉包と縮約: 到達可能性の関係を完全に保つトランジティブ閉包（全ての到達経路を直接辺で表したもの）や、冗長な辺を取り除くトランジティブ縮約（有限DAGでは一意）といった操作が意味を持ちます。
表現と基本アルゴリズム
DAGは隣接リストや隣接行列で表現できます。規模が大きく辺が疎な場合は隣接リストが効率的です。DAGに対してよく用いられるアルゴリズムをいくつか紹介します。
- トポロジカルソート — Kahnのアルゴリズム（入次数0の頂点を逐次取り除く）や深さ優先探索（DFS）を用いた方法があり、時間計算量は O(V + E) です。トポロジカル順序が得られれば、依存関係に基づく一方向の処理順序が決定できます。
- 閉路検出 — DFSで「後退辺（back edge）」の有無を調べることで有向サイクルを検出できます。Kahnのアルゴリズムで処理が途中で止まる（全頂点を取り除けない）場合もサイクル存在の指標になります。
- 最短・最長経路問題 — 一般の有向グラフでは難しい問題も、DAGではトポロジカル順序に従う動的計画法で O(V + E) に解けます。負の重みがある場合でも負のサイクルが無いので扱いやすい点が特徴です。
- トランジティブ閉包 — 各頂点からの到達可能性を求める処理で、繰り返しDFSやフロイド–ワーシャルなどを使う方法があります。大規模DAGではビットセットや行列乗算を使った高速化が行われます。
計算上の利点と困難性
DAGは「循環がない」という性質のおかげで、多くの計算問題が簡単になります。例として、トポロジカル順があるため動的計画法を一度の走査で適用でき、最長経路や最短経路、最小コストの順序決定などが効率的に解けます。一方で、DAG固有の困難性もあります。例えばトポロジカル順序の総数を数えることは #P-完全に関連する問題であり一般には難しいです。
実世界の応用例
DAGは「依存関係」や「因果関係」を表現するのに非常に適しているため、多くの分野で使われています。
- タスクスケジューリング・ワークフロー管理: Apache Airflow, Luigi などのワークフローツールはワークフローをDAGとして表現し、依存関係に基づいてジョブを順序実行します。ビルドシステム（例: Make、Bazel など）でも依存グラフは実質的にDAGです。
- バージョン管理（Git）: Gitのコミット履歴は親コミットへの参照（有向辺）を持ち、コミットグラフはDAGになります（分岐とマージはあってもサイクルは生じない）。
- 確率的グラフィカルモデル（ベイジアンネットワーク）: 条件付き独立性を表現するためにDAGが用いられ、因果推論にも広く利用されます。Judea Pearlらの因果推論理論でもDAGが基礎概念です。
- データフロー・計算グラフ: TensorFlow等の静的計算グラフや、ストリーム処理系のデータフローネットワークはしばしばDAGで表現され、最適な実行順序や並列化に利用されます（ただし動的ループや再帰は時間軸の展開によって別扱いになることがあります）。
- 分散台帳・DAG型ブロックチェーン: 従来のブロックチェーンとは異なり、IOTA（Tangle）やNano（block-lattice）などではトランザクションやブロックがDAG構造を採用して高スループット化を目指しています。
- プロジェクト管理: クリティカルパス法（CPM）やPERT図はプロジェクト内の作業依存関係をDAGで表し、最短完了時間や遅延許容度の解析に用います。
実装上の注意点と落とし穴
- 意図しない循環 — 依存関係を手動で管理する場合、気づかないうちに閉路が入り込むと処理が止まる・無限ループになるなど致命的です。CIやワークフロー定義では自動検出を組み込むべきです。
- トランジティブエッジの冗長性 — 到達可能性を保ちつつも直接的でない冗長なエッジが増えると可読性と管理性が悪化します。トランジティブ縮約で整理できる場合がありますが、縮約はコストがかかることもあります。
- スケーラビリティ — ノード数・辺数が巨大になるとトポロジカルソートや閉路検出そのものは線形アルゴリズムで可能でも、メモリやI/Oがボトルネックになります。分散処理やストリーミング処理を検討する必要があります。
- 表現力の限界 — フィードバックや双方向的な影響を持つシステム（例: 一部の制御系や相互監視のネットワーク）を直接DAGで表すことはできません。フィードバックを表す必要がある場合はモデル化方法の見直しが必要です。
設計上のヒント
- 依存関係を明確にし、可能な限り「単方向」で設計する。循環が必要ならば設計段階で明示的なループ処理（別レイヤー、タイムステップ毎の展開など）に置き換える。
- トポロジカル順序を保存しておくと、シリアライズや再実行時の順序決定が簡単になる。
- 大規模DAGではノードの粒度（細かすぎない）やエッジの削減を行い、可視性と解析性能を確保する。
- 自動化された検証（トポロジカルソートが可能か、入次数・出次数の極端な偏りがないか）をCIパイプラインに組み込む。
まとめ
有向非巡回ネットワーク（DAG）は、「因果関係」「依存関係」「順序」を自然に表現できる強力な抽象化です。トポロジカル順序や動的計画法といったアルゴリズム的利点により、スケジューリングや解析が効率的に行えます。実社会の多くのシステム（ワークフロー、バージョン管理、確率モデル、分散台帳など）でDAGが採用されているのはその表現力と計算上の取り扱いやすさが理由です。一方、循環（サイクル）や冗長エッジの管理、スケール対応など実装上の課題もあり、設計時にはこれらを意識する必要があります。
参考文献
- 有向非巡回グラフ（Wikipedia 日本語）
- Topological sorting（Wikipedia）
- Kahn's algorithm（Wikipedia）
- Directed acyclic graph — Applications（Wikipedia）
- Apache Airflow — Official documentation
- Pro Git（コミットグラフの解説）
- Bayesian network（Wikipedia）
- IOTA (Tangle) — DAG-based distributed ledger（Wikipedia）
- Judea Pearl, "Causality: Models, Reasoning and Inference"（因果推論の古典）
投稿者プロフィール
