Directed Acyclic Graph

Definition

Edges are directed, and there are no cycles.

The English name is Directed Acyclic Graph, abbreviated as DAG.

Properties

Any graph that can be topologically sorted must be a directed acyclic graph;

If there is a cycle, then any two nodes on the cycle cannot satisfy the condition in any sequence.
A directed acyclic graph can always be topologically sorted;

(Proof by induction) Assume that all directed acyclic graphs with no more than \(k\) nodes can be topologically sorted. Then for a graph with \(k\) nodes, consider the situation after performing the first step of topological sorting.

Determination

How to determine whether a graph is a directed acyclic graph?

Check whether it can be topologically sorted.

Of course, there are other methods. You can perform a DFS on the graph and check whether there are non-tree edges pointing to ancestors (back edges) in the resulting DFS tree. If such edges exist, then there is a cycle.

Applications

DP for Longest (Shortest) Path

On general graphs, the optimal time complexity for finding single-source longest (shortest) paths is \(O(nm)\) (Bellman–Ford algorithm, suitable for graphs with negative weights) or \(O(m \log m)\) (Dijkstra's algorithm, suitable for graphs without negative weights).

However, on DAGs, we can use DP to find the longest (shortest) path, optimizing the time complexity to \(O(n+m)\). The state transition equations are \(dis_v = \min(dis_v, dis_u + w_{u,v})\) or \(dis_v = \max(dis_v, dis_u + w_{u,v})\).

After topological sorting, traverse each node in topological order and use the current node to update subsequent nodes.

struct edge {
  int v, w;
};

int n, m;
vector<edge> e[MAXN];
vector<int> L;                               // Stores the topological sorting result
int max_dis[MAXN], min_dis[MAXN], in[MAXN];  // in stores the in-degree of each node

void toposort() {  // Topological sorting
  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) {  // Find single-source longest (shortest) paths starting from s
  toposort();     // Perform topological sorting first
  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);
    }
  }
}