DAG（有向非巡回グラフ）

DAG（Directed Acyclic Graph）は、有向閉路を持たない有向グラフ。

トポロジカルソートによって頂点を順序付けでき、DPなどを効率的に行える。

イメージ

text

辺の向きはすべて上から下とする。

例えば、次の辺を持つ。

0 → 1
0 → 2
1 → 3
2 → 3
3 → 4

このグラフには有向閉路が存在しないため、DAGである。

重要な性質

有向閉路が存在しない。
トポロジカルソートが可能。
トポロジカル順序は一意とは限らない。
空でないDAGには、入次数0の頂点と出次数0の頂点が必ず存在する。
DAG上の最長経路・最短経路をDPで求められる。
強連結成分分解（SCC）で各成分を縮約したグラフは必ずDAGになる。

典型的な解法

やりたいこと	解法
頂点を依存関係順に並べる	トポロジカルソート
有向閉路があるか判定	トポロジカルソート
最長経路を求める	DAG上のDP
最短経路を求める	トポロジカル順に緩和
経路の総数を数える	DAG上のDP
一般の有向グラフをDAGに変換	SCCで縮約

トポロジカルソート

すべての辺 u → v に対して、u が v より前に現れる順序を求める。

詳しくはトポロジカルソートを参照。

トポロジカル順序に沿って処理することで、遷移元の計算を終えてから遷移先を更新できる。

DAG上のDP

最長経路

辺の重みがないDAGで、最長経路の長さ（辺数）を求める。

dp[v] を、頂点vで終わるパスの最大長とする。

cpp

// orderはトポロジカルソート済み
vector<int> dp(n);
for (int v : order) {
    for (int nv : g[v]) {
        dp[nv] = max(dp[nv], dp[v] + 1);
    }
}
int ans = *max_element(dp.begin(), dp.end());

計算量：O(V+E)（トポロジカルソートを含む）

すべての頂点を開始地点にできるため、初期値は0でよい。

経路の数え上げ

始点sから各頂点への有向パスの数を求める。

cpp

const ll MOD = 998244353;
vector<ll> dp(n);
dp[s] = 1;

for (int v : order) {
    for (int nv : g[v]) {
        dp[nv] = (dp[nv] + dp[v]) % MOD;
    }
}

dp[v] は始点sから頂点vへのパスの数。

DAGなので、同じ頂点を何度も通ることはなく、トポロジカル順に足し合わせればよい。

最短経路

DAGなら、負辺があってもトポロジカル順に緩和することで最短距離を求められる。

cpp

vector<ll> dist(n, INFL);
dist[s] = 0;

for (int v : order) {
    if (dist[v] == INFL) continue;
    for (auto [nv, w] : g[v]) {
        dist[nv] = min(dist[nv], dist[v] + w);
    }
}

計算量：O(V+E)

※ 重み付き隣接リストを使用する例。距離のオーバーフローには注意する。

注意点

有向グラフであることが前提。
閉路が存在するとトポロジカルソートは全頂点を列挙できない。
トポロジカル順序が複数存在する場合もある。
DAGでは負辺があっても最短経路を線形時間で求められる。
DAG上の最長経路もDPで効率的に求められる。
DPの遷移方向とトポロジカル順序を合わせることが重要。
グラフが非連結でもDAGは成立する。

DAG（有向非巡回グラフ） ​

イメージ ​

重要な性質 ​

典型的な解法 ​

トポロジカルソート ​

DAG上のDP ​

最長経路 ​

経路の数え上げ ​

最短経路 ​

注意点 ​

関連 ​