跳转至

# 有向无环图

## 定义

边有向，无环．

英文名叫 Directed Acyclic Graph，缩写是 DAG．

## 性质

- 能 拓扑排序 的图，一定是有向无环图；

  如果有环，那么环上的任意两个节点在任意序列中都不满足条件了．

- 有向无环图，一定能拓扑排序；

  （归纳法）假设节点数不超过 𝑘 k 的 有向无环图都能拓扑排序，那么对于节点数等于 𝑘 k 的，考虑执行拓扑排序第一步之后的情形即可．

## 判定

如何判定一个图是否是有向无环图呢？

检验它是否可以进行 拓扑排序 即可．

当然也有另外的方法，可以对图进行一遍 DFS，在得到的 DFS 树上看看有没有连向祖先的非树边（返祖边）．如果有的话，那就有环了．

## 应用

### DP 求最长（短）路

在一般图上，求单源最长（短）路径的最优时间复杂度为 𝑂(𝑛 𝑚)O(n m)（Bellman–Ford 算法，适用于有负权图）或 𝑂(𝑚 l o g⁡𝑚)O(m log⁡m)（Dijkstra 算法，适用于无负权图）．

但在 DAG 上，我们可以使用 DP 求最长（短）路，使时间复杂度优化到 𝑂(𝑛 +𝑚)O(n+m)．状态转移方程为 𝑑 𝑖 𝑠 𝑣 =𝑚 𝑖 𝑛(𝑑 𝑖 𝑠 𝑣,𝑑 𝑖 𝑠 𝑢 +𝑤 𝑢,𝑣)d i s v=m i n(d i s v,d i s u+w u,v) 或 𝑑 𝑖 𝑠 𝑣 =𝑚 𝑎 𝑥(𝑑 𝑖 𝑠 𝑣,𝑑 𝑖 𝑠 𝑢 +𝑤 𝑢,𝑣)d i s v=m a x(d i s v,d i s u+w u,v)．

拓扑排序后，按照拓扑序遍历每个节点，用当前节点来更新之后的节点．

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    struct edge {
      int v, w;
    };

    int n, m;
    vector<edge> e[MAXN];
    vector<int> L;                               // 存储拓扑排序结果
    int max_dis[MAXN], min_dis[MAXN], in[MAXN];  // in 存储每个节点的入度

    void toposort() {  // 拓扑排序
      queue<int> S;
      memset(in, 0, sizeof(in));
      for (int i = 1; i <= n; i++) {
        for (int j = 0; j < e[i].size(); j++) {
          in[e[i][j].v]++;
        }
      }
      for (int i = 1; i <= n; i++)
        if (in[i] == 0) S.push(i);
      while (!S.empty()) {
        int u = S.front();
        S.pop();
        L.push_back(u);
        for (int i = 0; i < e[u].size(); i++) {
          if (--in[e[u][i].v] == 0) {
            S.push(e[u][i].v);
          }
        }
      }
    }

    void dp(int s) {  // 以 s 为起点求单源最长（短）路
      toposort();     // 先进行拓扑排序
      memset(min_dis, 0x3f, sizeof(min_dis));
      memset(max_dis, 0, sizeof(max_dis));
      min_dis[s] = 0;
      for (int i = 0; i < L.size(); i++) {
        int u = L[i];
        for (int j = 0; j < e[u].size(); j++) {
          min_dis[e[u][j].v] = min(min_dis[e[u][j].v], min_dis[u] + e[u][j].w);
          max_dis[e[u][j].v] = max(max_dis[e[u][j].v], max_dis[u] + e[u][j].w);
        }
      }
    }

参见：DAG 上的 DP．

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Ir1d, Enter-tainer, ouuan, Tiphereth-A, billchenchina, dong628, HeRaNO
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用