有向无环图


定义

边有向,无环。

英文名叫 Directed Acyclic Graph,缩写是 DAG。

性质

  • 拓扑排序 的图,一定是有向无环图;

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

  • 有向无环图,一定能拓扑排序;

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

判定

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

检验它是否可以进行

拓扑排序 即可。

当然也有另外的方法,可以对图进行一遍

DFS,在得到的 DFS 树上看看有没有连向祖先的非树边(返祖边)。如果有的话,那就有环了。

应用

DP 求最长(短)路

在一般图上,求单源最长(短)路径的最优时间复杂度为

Bellman-Ford 算法,适用于有负权图)或
Dijkstra 算法
,适用于无负权图)。

但在 DAG 上,我们可以使用 DP 求最长(短)路,使时间复杂度优化到 。状态转移方程为

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

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

贡献者:@Yufan@Jinglei@mgt@ouuan@Ir1d@HeRaNO

本页面最近更新:2/3/2023, 12:00:00 AM更新历史

发现错误?想一起完善? 在 GitHub 上编辑此页!

本页面的全部内容在 CC BY-SA 4.0SATA 协议之条款下提供,附加条款亦可能应用

评论

0 条评论
未登录用户


Copyright © 2016 - 2023 OI Wiki Team

最近更新:fd2ec2c, 2023-02-03

联系方式:Telegram 群组 / QQ 群组