Directed acyclic graphs (DAGs)

A directed acyclic graph (DAG) is a directed graph that contains no directed cycles: you cannot follow arcs forward and return to the same vertex. DAGs model dependencies, hierarchies, and stages where every edge goes "forward" in some consistent order—often captured by a topological ordering. They are the sweet spot between arbitrary digraphs (which may deadlock with cycles) and trees (which forbid sharing children).

1) Definition

A finite directed graph G = (V, E) is a DAG if there is no sequence of distinct vertices v0, v1, …, vk with k ≥ 1 such that (vi, vi+1) ∈ E for all i and vk = v0. Equivalently: the graph has no directed cycle.

2) Useful characterizations

• Topological order: A finite digraph is a DAG if and only if it admits a topological ordering—a linear ordering of vertices such that every arc goes from earlier to later in the list.
• DFS coloring: Run DFS with states white / gray / black. The graph is acyclic if and only if no arc leads from a gray vertex to another gray vertex (no back edge in the DFS classification).
• Strongly connected components: In a DAG, each SCC is a single vertex (there is no directed cycle inside any nonempty subset).

3) Sources and sinks

• Source: vertex with indegree 0 (no incoming arcs).
• Sink: vertex with outdegree 0 (no outgoing arcs).
• Every nonempty finite DAG has at least one source and at least one sink—useful starting points for topological algorithms.

4) Pictures

DAG (linear pipeline):     0 --> 1 --> 2

Not a DAG (2-cycle):        0 --> 1
                            ^     |
                            +-----+   (arcs 0->1 and 1->0)

Diamond DAG (C example):    0 --> 1 --\
                            |       \--> 3 --> 4
                            '--> 2 --/

5) Quick comparison

6) Where DAGs appear

• Build systems & package managers — module A depends on B.
• Instruction scheduling & compilers — value dependencies between operations.
• Dynamic programming on graphs — when subproblems form a DAG, you can evaluate in topological order.
• Causal / precedence — event A must occur before B.

7) C — "Is this digraph a DAG?"

Adjacency matrix adj[u][v] = 1 if u → v. Three colors: 0 white, 1 gray (on recursion stack), 2 black (done).

#include <stdio.h>
#include <string.h>

#define V 5
int adj[V][V];
/* color: 0 white, 1 gray, 2 black */
int color[V];

/* Returns 1 if subtree from u is acyclic so far */
static int dfs(int u) {
    color[u] = 1;
    for (int v = 0; v < V; v++) {
        if (!adj[u][v]) continue;
        if (color[v] == 1) return 0;   /* back edge → directed cycle */
        if (color[v] == 0 && !dfs(v)) return 0;
    }
    color[u] = 2;
    return 1;
}

int is_dag(void) {
    memset(color, 0, sizeof color);
    for (int i = 0; i < V; i++)
        if (color[i] == 0 && !dfs(i))
            return 0;
    return 1;
}

int main(void) {
    /* Diamond DAG: 0->1, 0->2, 1->3, 2->3, 3->4 */
    adj[0][1] = adj[0][2] = 1;
    adj[1][3] = adj[2][3] = 1;
    adj[3][4] = 1;
    printf("is_dag = %d\n", is_dag());   /* expect 1 */
    return 0;
}

8) Complexity

Cycle detection / DAG check with DFS: O(V + E) time and O(V) auxiliary space for colors and recursion stack (adjacency list); with a dense matrix stored as shown, scanning a row is O(V) per edge relaxation—still fine for teaching-sized V.

9) Trace — DFS on the diamond DAG

Vertices 0→1, 0→2, 1→3, 2→3, 3→4. Start DFS at 0, neighbors in increasing index order.

10) Contrast — one arc creates a cycle

Add arc 4 → 0 to the previous graph. Then DFS eventually sees an edge into gray 0 → not a DAG.