有向無環圖

定義

邊有向，無環。

英文名叫 Directed Acyclic Graph，縮寫是 DAG。

性質

• 能 拓撲排序 的圖，一定是有向無環圖；

  如果有環，那麼環上的任意兩個節點在任意序列中都不滿足條件了。

• 有向無環圖，一定能拓撲排序；

  （歸納法）假設節點數不超過 \(k\) 的 有向無環圖都能拓撲排序，那麼對於節點數等於 \(k\) 的，考慮執行拓撲排序第一步之後的情形即可。

判定

如何判定一個圖是否是有向無環圖呢？

檢驗它是否可以進行 拓撲排序 即可。

當然也有另外的方法，可以對圖進行一遍 DFS，在得到的 DFS 樹上看看有沒有連向祖先的非樹邊（返祖邊）。如果有的話，那就有環了。

應用

DP 求最長（短）路

在一般圖上，求單源最長（短）路徑的最優時間複雜度為 \(O(nm)\)（Bellman–Ford 算法，適用於有負權圖）或 \(O(m \log m)\)（Dijkstra 算法，適用於無負權圖）。

但在 DAG 上，我們可以使用 DP 求最長（短）路，使時間複雜度優化到 \(O(n+m)\)。狀態轉移方程為 \(dis_v = min(dis_v, dis_u + w_{u,v})\) 或 \(dis_v = max(dis_v, dis_u + w_{u,v})\)。

拓撲排序後，按照拓撲序遍歷每個節點，用當前節點來更新之後的節點。

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。

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用