データ構造の基礎：非循環有向グラフ（DAG）とは？定義・性質・具体例を徹底解説

非循環有向グラフ（DAG）とは

非循環有向グラフ（Acyclic Digraph）とは、有向サイクル（閉路）を一切含まない有向グラフのことを指します。英語では「Directed Acyclic Graph」と表記され、その頭文字を取ってDAGと略されるのが一般的です。

DAGにおいては、どのノードから出発して辺を辿っていっても、二度と同じノードに戻ることがないという点が最大の特徴です。

DAGの重要な性質

すべての有限のDAGには、出次数（そのノードから出ていく辺の数）が0であるノードが少なくとも1つ存在することが数学的に証明されています。これはDAGの最も基本的な性質の一つです。

また、これに関連して次のような性質も成り立ちます。

• 出次数0のノードが必ず存在する：グラフの終端となるノードが必ずあります。
• 入次数0のノードも必ず存在する：グラフの始点となるノードも必ずあります。
• トポロジカルソートが可能：すべてのノードを依存関係に反しない順序で一列に並べることができます。

DAGの具体例

1つのノードからなるDAGの例

ノードが1つだけの場合、辺が存在しないためサイクルが発生しようがなく、自動的にDAGとなります。このとき、唯一のノードの出次数は0です。

2つのノードからなるDAGの例

2つのノード間に片方向の辺が張られている場合はDAGですが、もし双方向の辺（A→B と B→A の両方）が存在すると、それはサイクルとなるためDAGではなくなります。

3つのノードからなるDAGの例

3つのノードで構成される場合でも、すべての辺が一方向へ流れていれば、どの経路を辿っても出発点に戻ることはありません。このため、全体としてサイクルを持たないDAGとなります。

DAGの主な応用分野

DAGは理論上の概念にとどまらず、実際のコンピュータサイエンスのさまざまな場面で活用されています。

• タスクスケジューリング：タスク間の依存関係を表現し、実行順序を決定します。
• ビルドシステム：Makeなどのツールがファイル間の依存関係をDAGで管理し、必要な処理だけを実行します。
• バージョン管理システム：Gitのコミット履歴はDAGとして表現されます。
• データ処理パイプライン：Apache Sparkなどの分散処理フレームワークでは、処理の流れがDAGで構成されます。
• 式の評価・コンパイラ最適化：共通部分式の重複計算を避けるために利用されます。

まとめ

非循環有向グラフ（DAG）は「有向サイクルを持たない有向グラフ」であり、有限のDAGには必ず出次数0のノードが存在するという重要な性質を持ちます。このシンプルな構造ゆえに、依存関係の管理や処理順序の決定など、幅広い分野で応用されている非常に重要なデータ構造です。