Directed Acyclic Graph

Definition

Its edges are directed, and it contains no cycles.

Its English name is Directed Acyclic Graph, abbreviated DAG.

Properties

• A graph that can be topologically sorted must be a directed acyclic graph.

  If there is a cycle, then any two vertices on the cycle fail to satisfy the condition in every sequence.

• A directed acyclic graph can always be topologically sorted.

  (By induction) Assume that every directed acyclic graph with at most $k$ vertices can be topologically sorted. For a graph with $k$ vertices, consider the situation after performing the first step of topological sorting.

Recognition

How can we determine whether a graph is a directed acyclic graph?

It is sufficient to check whether it can be topologically sorted.

There is also another method: run a DFS on the graph and check the resulting DFS tree for a nontree edge directed to an ancestor (a back edge). If one exists, the graph contains a cycle.

Applications

Finding longest (shortest) paths with DP

In a general graph, the optimal time complexity for finding a single-source longest (shortest) path is $O(nm)$ (the Bellman–Ford algorithm, suitable for graphs with negative edge weights) or $O(m \log m)$ (Dijkstra's algorithm, suitable for graphs with nonnegative edge weights).

However, on a DAG, we can use DP to find longest (shortest) paths and reduce the time complexity to $O(n+m)$. The state transition is $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 vertex in topological order and use the current vertex to update subsequent vertices.

struct edge {
  int v, w;
};

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

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 from s
  toposort();     // first perform topological sorting
  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);
    }
  }
}

See DP on DAGs.