1 有向非巡回グラフの基本概念
1.1 有向グラフの定義
有向グラフは、頂点集合と辺集合の組で表され、各辺は始点と終点の向きをもつ。ある頂点から別の頂点へ向かう“流れ”を区別できるため、依存関係や処理の順序など「方向性のある関係」をモデル化するのに適している。
数学的には、頂点集合を \(V\)、有向辺の集合を \(E\) とし、各辺は順序対 \((u,v)\) として表される（\(u\) から \(v\) へ向かう辺）。
1.2 非巡回性（閉路がないこと）
1.2.1 有向サイクルの概念
有向サイクル（閉路）とは、頂点の列 \(v_1, v_2, \dots, v_k\)（\(k\ge 1\)）が存在し、各 \(v_i\) から \(v_{i+1}\)（ただし \(v_{k+1}=v_1\)）へ向かう有向辺がすべて含まれている状態を指す。 このとき、方向に沿って辿れば最初の頂点へ戻れるため、処理の先後関係が「循環」して矛盾が生じやすい。
1.2.2 非巡回性の判定観点
非巡回性は「閉路が存在しない」ことと同義である。判定の基本的な考え方は、（1）閉路を形成するような到達の往復がないかを見る、または（2）順序付けを試みて矛盾が起きないかを見る、のいずれかに整理できる。 実務では、後述するトポロジカル順序生成の過程で、処理可能な頂点が枯渇するかどうかを観察する手法がよく用いられる。
1.3 用語と表記
1.3.1 頂点・辺・入次数・出次数
頂点は状態やタスク、データ生成点などを表す。辺は依存や変換の向きを示す。 入次数は、ある頂点へ向かっている辺の数であり「その頂点の前に必要なものの有無」を反映する指標になる。出次数は、その頂点から出ていく辺の数であり「その頂点の結果がどこへ影響するか」を表す。
1.3.2 近傍と到達の考え方
近傍は、隣接する頂点（有向辺により直接到達できる頂点）を指す。通常は向きに沿って「次に辿れる集合」を考える。 到達可能性は、辺の向きに従って連鎖的に辿った結果、ある頂点へ到達できるかどうかである。非巡回性は、この到達関係が循環せず、階層的に整理できることを意味する。
2 構造特性と理論的性質
2.1 トポロジカル順序
2.1.1 一意性と複数存在
トポロジカル順序は、頂点を並べた列であって、任意の有向辺 \((u,v)\) に対し、並びで \(u\) が \(v\) より前に現れる性質をもつ。 DAGでは必ず少なくとも1つのトポロジカル順序が存在する。ただし一般に一意ではなく、独立した部分構造（相互に依存しない頂点群）があると、並び替えによる複数の順序が生じる。
2.1.1.1 Kahn法の考え方（概要）
Kahn法は、入次数が0の頂点を順に取り出し、その頂点から出る辺を“削除した”として入次数を更新していくことでトポロジカル順序を構成する。 全頂点が取り出せるなら非巡回であり、途中で入次数0の頂点が存在しなくなる場合は閉路があることを示す。順序は、入次数0の頂点が複数あるときに選択が分岐して複数になり得る。
2.1.2 順序が意味する依存関係
トポロジカル順序は、辺の向きを「前に処理されるべき関係」として読み替えることで意味を得る。例えば、あるタスクが別のタスクに依存するなら、依存先が順序上で必ず後になり、実行計画が矛盾なく組める。 この対応により、計算順序や参照の整合性を形式化できる。
2.2 推移性と到達可能性
2.2.1 到達可能性の判定
到達可能性の判定は、始点から向きに沿って辿って目的地に到達できるかを問う。典型的には探索（深さ優先探索や幅優先探索）が用いられる。 DAGでは閉路がないため、探索が無限に続くことがなく、各辺・頂点を有限回で処理できる。さらに、トポロジカル順序に基づいて到達集合を累積させるなど、動的手法も組み合わせやすい。
2.2.2 部分順序としての見方
DAGの到達関係は、推移律を満たす形で整理できる。つまり、「ある頂点から別の頂点へ到達できる」という関係は、状況によっては反射性や反対称性を補う定義により、部分順序（poset）的な見方が可能になる。 この観点では、トポロジカル順序は部分順序の線形拡張として解釈でき、階層構造の理解に役立つ。
2.3 性質の比較（DAGと一般有向グラフ）
2.3.1 閉路の有無による違い
一般有向グラフには閉路があり得る。閉路が存在すると、辺の向きをそのまま「先行条件」とみなした際に、同じ頂点を起点として再度到達できるため、単純な順序付けが困難になる。 DAGでは閉路がないため、依存の方向を矛盾なく並べ直せる点が決定的な違いとなる。
2.3.2 計算上の影響
閉路がある場合、実行計画や順序生成では検出・解消が必要になることが多い。対してDAGでは、トポロジカル順序の生成や順序に沿った集計が成立しやすい。 また、動的計画法のように「前に計算した結果を後へ伝播する」方式を安全に適用できるため、設計と実装が整理されやすい。
3 表現方法とアルゴリズム
3.1 グラフの表現
3.1.1 隣接リスト
隣接リストは、各頂点に対して出ていく辺（隣接先）の集合を保持する方式である。疎なグラフで効率が良く、探索時に必要な辺だけを辿れる。 メモリ使用量は概ね辺数に比例しやすい。
3.1.2 隣接行列
隣接行列は、頂点数 \(n\) に対し \(n\times n\) の行列で「辺の有無」を表す。判定（ある辺が存在するか）を高速に行える一方で、頂点が多いと記憶量が大きくなる。 密なグラフでの計算に向くが、DAGに限らず一般に入力特性に依存する。
3.1.3 辺のリスト表現
辺のリスト表現は、全ての有向辺を \((u,v)\) の列として保持する形である。読み込みや記録に向き、アルゴリズムによっては必要な情報を一度集計してから処理する。 入次数の計算などは辺リストから直接可能である。
3.2 トポロジカル順序の生成
3.2.1 典型アルゴリズム（概要）
代表的な方法はKahn法と、深さ優先探索に基づく後順序（並び替え）により構成する方式である。どちらもDAGでは必ず全頂点を並べられる。 Kahn法は入次数を中心に扱い、探索型の方式は再帰やスタックを通じて辺の依存を解消する。
3.2.2 実装上の注意点
トポロジカル順序生成では、入次数更新や訪問済み管理が重要になる。並列実装する場合、入次数0の頂点集合の扱いで競合が生じ得るため、キューの実装方針や同期戦略を検討する。 また、入力が本当にDAGか不明な場合は、全頂点が出力できたかどうかで閉路の有無を判断するのが一般的である。
3.3 DAG上の代表的な処理
3.3.1 動的計画法の基礎（順序に沿う計算）
DAGでは、トポロジカル順序を利用して「必要な前計算が常に先に存在する」構造を作れる。これにより、状態 \(dp[v]\) を前の頂点から集計し、順序の進行とともに値を確定できる。 計算の正当性は、依存が逆向きに戻らない性質から保証される。
3.3.2 最長経路・最短経路の考え方（DAG向け）
重み付きDAGでは、トポロジカル順序に沿って緩和（更新）を行うことで最長や最短を求める設計が可能になる。閉路がないため、負閉路のような問題設定が不要になりやすい。 方向性に従って一度ずつ更新する枠組みが取りやすく、計算量を安定させられる。
3.3.3 到達可能性の効率的な見積もり
到達可能性は、単一始点なら探索で十分な場合が多い。一方、多数の問い合わせがある場合は、トポロジカル順序に基づく集計（到達集合の伝播）や、到達情報の圧縮表現を検討する余地がある。 ただし到達集合をそのまま保持すると計算量が増えるため、要件に応じた妥協点（精度、更新頻度、記憶量）を設計する。
4 応用と実例
4.1 タスクの依存関係管理
4.1.1 ビルドシステムやワークフロー
ビルドシステムでは、あるソースや生成物が別の生成物に依存する関係をDAGとして記述し、依存先が生成されてから後続処理を実行する。 ワークフローでも、承認や前処理の完了を条件として次段を進める設計が可能で、実行順の衝突を避けやすい。
4.1.2 依存解決と実行計画
依存解決では、入力された関係からトポロジカル順序を求め、実行計画を組み立てる。実行計画は、順序に加えて同時実行の可能性（独立タスクの集合）を反映できる。 また、依存関係が更新された際には、閉路が混入していないかの検査としてもDAGの性質が利用される。
4.2 データ処理パイプライン
4.2.1 変換処理と段階的実行
データ処理では、抽出・変換・集約などの段階を段階間の依存として表し、上流の生成結果に基づいて下流処理を動かす。DAGとして表現すると、どの工程が完了すれば次が動かせるかを明確にできる。 この形式は、パイプラインの拡張や工程の差し替えにも向く。
4.2.2 キャッシュや再計算戦略
キャッシュ戦略では、ある工程の入力が変わった場合に、影響を受ける下流工程だけを再計算する。影響範囲は到達関係として表せるため、DAGが持つ構造を利用した効率化が可能になる。 再計算を最小化することはコスト削減につながり、運用設計の中心課題になる。
4.3 ソフトウェア設計への適用
4.3.1 モジュール依存と参照関係
モジュール間の依存（ライブラリの参照、設定の上位互換など）を有向関係として捉えると、依存の方向が一方的に進む構造を作れる。モジュールを階層化できる場合、DAGとして整理することで設計の見通しが良くなる。 依存の循環が起きると、ビルドや理解の両面で障害となりやすいため、非巡回性は実務上の利点になる。
4.3.2 仕様の整合性確認（依存の矛盾検出）
仕様に含まれる制約が依存関係として表現できる場合、DAGでない（閉路がある）なら整合性が欠けている可能性が高い。例えば「AがBを要求し、BもAを要求する」といった循環があれば、解決不能な条件になり得る。 そのため、トポロジカル順序生成の失敗は、矛盾の検出手掛かりとなる。
4.4 実装・運用のベストプラクティス
4.4.1 追加・削除時の非巡回性維持
更新操作では、辺や頂点を追加した瞬間に閉路が混入し得る。運用では、変更点に対応する範囲だけを再評価し、必要に応じて影響する部分構造を検査する設計が望ましい。 全面再計算が高コストなら、到達関係や入次数の増減を手がかりに局所的に検討する。
4.4.2 可視化とデバッグ手法
DAGは描画して理解することで、依存の流れが直感的に把握できる。可視化では、層（トポロジカル順序の段）ごとに配置することで、ボトルネックや独立部分を見つけやすくなる。 デバッグでは、閉路が疑われる入力に対し、トポロジカル順序生成がどの段階で詰まったか、あるいは影響する頂点群がどこかを手繰ると原因特定が進む。