34.01Intermediate / Advanced4 topics14 min4 interactive animations

Directed graph fundamentals

The vocabulary of directed graphs that the rest of the chapter relies on: in-degree and out-degree, sources and sinks, directed cycles, and what reversing every arrow does.

Learning goals

Count in-degree and out-degree and find sources and sinks
Recognise a directed cycle and explain why sources prevent it
Reverse a graph and say what the reversal is used for

Prerequisites

Graph vocabularyGraph representationsDepth-first search

A task list where each task may depend on others is a directed graph: an arrow from a to b means a must happen first. Whether the work can be done at all depends on cycles, and which tasks can start immediately depends on sources.

34.01.1

In-degree/out-degree

In a directed graph every arrow has a *tail* (where it starts) and a *head* (where it ends). The **out-degree** of a vertex counts the arrows leaving it, the **in-degree** counts those arriving. Unlike the undirected case there are two numbers per vertex, and each arrow adds 1 to exactly one out-degree and one in-degree, so both lists add up to the number of arrows.

Open the animation with the first option: each arrow read raises one out-degree and one in-degree. A self-loop a → a adds 1 to both numbers of the same vertex.

Java

1static int[][] degrees(List<List<Integer>> g) {       // {in-degree, out-degree} per vertex
2    int n = g.size();
3    int[] in = new int[n], out = new int[n];
4    for (int u = 0; u < n; u++)
5        for (int v : g.get(u)) { out[u]++; in[v]++; }
6    return new int[][]{in, out};
7}

Directed graph facts: degrees, sources, sinks, descendants and ancestors

Interactive · edit the input

directed graph · 6 vertices · 6 edges

Arrow being read / vertex being expandedSource (in-degree 0)ReachedSink (out-degree 0)

in-degree

out-degree

Setup

Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.

Step 1 / 8

Java

1int[][] degrees(List<List<Integer>> g) {         // {in-degree, out-degree} per vertex
2    int n = g.size(); int[] in = new int[n], out = new int[n];
3    for (int u = 0; u < n; u++) for (int v : g.get(u)) { out[u]++; in[v]++; }
4    return new int[][]{in, out};                 // source: in == 0, sink: out == 0
5}
6List<Integer> descendants(List<List<Integer>> g, int s) {   // reached by one or more arrows
7    boolean[] seen = new boolean[g.size()];
8    Deque<Integer> stack = new ArrayDeque<>(g.get(s));
9    List<Integer> found = new ArrayList<>();
10    while (!stack.isEmpty()) {
11        int u = stack.pop();
12        if (seen[u]) continue;
13        seen[u] = true; found.add(u);
14        for (int v : g.get(u)) stack.push(v);
15    }
16    return found;                                // contains s only when s lies on a cycle
17}
18// ancestors(g, s) = descendants(reverse(g), s)

Live state

0 arrows read0 vertices reached

arrows

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	n=6 arrows=6	Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.
2	L3	arrow=0 → 1 out[a]=1 in[b]=1	Arrow 0 → 1: out-degree of 0 is now 1, in-degree of 1 is now 1.
3	L3	arrow=0 → 2 out[a]=2 in[b]=1	Arrow 0 → 2: out-degree of 0 is now 2, in-degree of 2 is now 1.
4	L3	arrow=1 → 3 out[a]=1 in[b]=1	Arrow 1 → 3: out-degree of 1 is now 1, in-degree of 3 is now 1.
5	L3	arrow=2 → 3 out[a]=1 in[b]=2	Arrow 2 → 3: out-degree of 2 is now 1, in-degree of 3 is now 2.
6	L3	arrow=2 → 4 out[a]=2 in[b]=1	Arrow 2 → 4: out-degree of 2 is now 2, in-degree of 4 is now 1.
7	L3	arrow=3 → 5 out[a]=1 in[b]=1	Arrow 3 → 5: out-degree of 3 is now 1, in-degree of 5 is now 1.
8	L4	return=in [0, 1, 1, 2, 1, 1] out [2, 1, 2, 1, 0, 0] sources [0] sinks [4, 5]	Sources (in-degree 0): [0]. Sinks (out-degree 0): [4, 5]. The in-degrees add up to 6, the out-degrees to 6: both equal the 6 arrows.

34.01.2

Sources/sinks

A **source** has in-degree 0: nothing points to it. A **sink** has out-degree 0: it points to nothing. In a task graph the sources are the tasks that can start right now, and the sinks are the final results that nothing else waits for.

A directed graph with no source at all must contain a cycle: start anywhere and keep stepping backwards along an incoming arrow; with finitely many vertices you must repeat one. The converse is false, because a graph can have a source and still contain a cycle elsewhere. The preset *A cycle: no sources at all* shows the first fact.

Java

1static List<List<Integer>> sourcesAndSinks(List<List<Integer>> g) {   // {sources, sinks}
2    int n = g.size();
3    int[] in = new int[n];
4    for (List<Integer> out : g) for (int v : out) in[v]++;
5    List<Integer> sources = new ArrayList<>(), sinks = new ArrayList<>();
6    for (int v = 0; v < n; v++) {
7        if (in[v] == 0) sources.add(v);
8        if (g.get(v).isEmpty()) sinks.add(v);
9    }
10    return List.of(sources, sinks);
11}

Directed graph facts: degrees, sources, sinks, descendants and ancestors

Interactive · edit the input

directed graph · 6 vertices · 6 edges

Arrow being read / vertex being expandedSource (in-degree 0)ReachedSink (out-degree 0)

in-degree

out-degree

Setup

Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.

Step 1 / 8

Java

1int[][] degrees(List<List<Integer>> g) {         // {in-degree, out-degree} per vertex
2    int n = g.size(); int[] in = new int[n], out = new int[n];
3    for (int u = 0; u < n; u++) for (int v : g.get(u)) { out[u]++; in[v]++; }
4    return new int[][]{in, out};                 // source: in == 0, sink: out == 0
5}
6List<Integer> descendants(List<List<Integer>> g, int s) {   // reached by one or more arrows
7    boolean[] seen = new boolean[g.size()];
8    Deque<Integer> stack = new ArrayDeque<>(g.get(s));
9    List<Integer> found = new ArrayList<>();
10    while (!stack.isEmpty()) {
11        int u = stack.pop();
12        if (seen[u]) continue;
13        seen[u] = true; found.add(u);
14        for (int v : g.get(u)) stack.push(v);
15    }
16    return found;                                // contains s only when s lies on a cycle
17}
18// ancestors(g, s) = descendants(reverse(g), s)

Live state

0 arrows read0 vertices reached

arrows

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	n=6 arrows=6	Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.
2	L3	arrow=0 → 1 out[a]=1 in[b]=1	Arrow 0 → 1: out-degree of 0 is now 1, in-degree of 1 is now 1.
3	L3	arrow=0 → 2 out[a]=2 in[b]=1	Arrow 0 → 2: out-degree of 0 is now 2, in-degree of 2 is now 1.
4	L3	arrow=1 → 3 out[a]=1 in[b]=1	Arrow 1 → 3: out-degree of 1 is now 1, in-degree of 3 is now 1.
5	L3	arrow=2 → 3 out[a]=1 in[b]=2	Arrow 2 → 3: out-degree of 2 is now 1, in-degree of 3 is now 2.
6	L3	arrow=2 → 4 out[a]=2 in[b]=1	Arrow 2 → 4: out-degree of 2 is now 2, in-degree of 4 is now 1.
7	L3	arrow=3 → 5 out[a]=1 in[b]=1	Arrow 3 → 5: out-degree of 3 is now 1, in-degree of 5 is now 1.
8	L4	return=in [0, 1, 1, 2, 1, 1] out [2, 1, 2, 1, 0, 0] sources [0] sinks [4, 5]	Sources (in-degree 0): [0]. Sinks (out-degree 0): [4, 5]. The in-degrees add up to 6, the out-degrees to 6: both equal the 6 arrows.

34.01.3

Directed cycles

A **directed cycle** is a path that returns to its starting vertex following the arrows, such as a → b → c → a. A graph with no directed cycle is a **DAG** (directed acyclic graph). Unlike undirected graphs, the two arrows a → b and b → a form a cycle of length 2, and a self-loop is a cycle of length 1.

DFS with three colours finds one: an arrow to a grey vertex (still on the recursion stack) closes a cycle. The animation, set to *cycle detection with three colours*, shows both a hit and an acyclic run. The next lesson finds cycles another way, with Kahn's algorithm.

Java

1static boolean containsCycle(List<List<Integer>> g) {
2    int[] colour = new int[g.size()];                  // 0 white, 1 grey (on the stack), 2 black
3    for (int s = 0; s < g.size(); s++)
4        if (colour[s] == 0 && grey(g, s, colour)) return true;
5    return false;
6}
7static boolean grey(List<List<Integer>> g, int u, int[] colour) {
8    colour[u] = 1;
9    for (int v : g.get(u)) {
10        if (colour[v] == 1) return true;               // arrow back into the stack
11        if (colour[v] == 0 && grey(g, v, colour)) return true;
12    }
13    colour[u] = 2;
14    return false;
15}

Depth-first search: times, tree, edge classes, three colours

Interactive · edit the input

undirected graph · 6 vertices · 6 edges

White: undiscoveredGrey: on the stackBlack: finishedTree edgeBack edgeForward edge

stack (bottom to top)

empty

discovery / finish time

-0

-1

-2

-3

-4

-5

Setup

Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.

Step 1 / 15

Java

1int[] disc, fin; int time;
2void dfs(List<List<Integer>> g, int u) {         // recursive
3    disc[u] = ++time;                            // u turns grey
4    for (int v : g.get(u))
5        if (disc[v] == 0) dfs(g, v);             // tree edge: go deeper
6    fin[u] = ++time;                             // u turns black
7}
8void dfsIterative(List<List<Integer>> g, int s) {
9    int[] next = new int[g.size()];              // position in each vertex's neighbour list
10    Deque<Integer> stack = new ArrayDeque<>();
11    disc[s] = ++time; stack.push(s);
12    while (!stack.isEmpty()) {
13        int u = stack.peek();
14        if (next[u] < g.get(u).size()) {
15            int v = g.get(u).get(next[u]++);
16            if (disc[v] == 0) { disc[v] = ++time; stack.push(v); }
17        } else { fin[u] = ++time; stack.pop(); }
18    }
19}
20// directed graphs: classify the edge u -> v when it is examined
21String classify(int u, int v) {
22    if (disc[v] == 0) return "tree";
23    if (fin[v] == 0) return "back";              // v is still on the stack (grey): a cycle
24    return disc[u] < disc[v] ? "forward" : "cross";
25}

Live state

0 tree edges0 back edges0 forward edges0 cross edges

start

No condition evaluated on this step

Execution trace (dry run table)Show 15 steps

Step	Line	State	What happens
1	L1	start=0	Depth-first search follows an edge to a new vertex as long as it can, and backs up only when a vertex has no unexplored neighbour. White = undiscovered, grey = on the current path, black = finished.
2	L3	u=0 disc[u]=1 time=1	Discover 0 at time 1: it turns grey and goes on the stack (a new DFS tree starts here).
3	L5	u=0 v=1 disc[v]=2	0 - 1: 1 is white, so this is a tree edge. Discover 1 at time 2: it turns grey, and the search goes deeper.
4	L5	u=1 v=3 disc[v]=3	1 - 3: 3 is white, so this is a tree edge. Discover 3 at time 3: it turns grey, and the search goes deeper.
5	L5	u=3 v=2 disc[v]=4	3 - 2: 2 is white, so this is a tree edge. Discover 2 at time 4: it turns grey, and the search goes deeper.
6	L5	u=2 v=0 class=back	2 - 0: 0 is grey, still on the stack: an edge to an ancestor, a back edge. It closes a cycle.
7	L6	v=2 fin[v]=5 time=5	2 has no unexplored neighbour left: it turns black at time 5 and is popped. Back to 3.
8	L5	u=3 v=4 disc[v]=6	3 - 4: 4 is white, so this is a tree edge. Discover 4 at time 6: it turns grey, and the search goes deeper.
9	L5	u=4 v=5 disc[v]=7	4 - 5: 5 is white, so this is a tree edge. Discover 5 at time 7: it turns grey, and the search goes deeper.
10	L6	v=5 fin[v]=8 time=8	5 has no unexplored neighbour left: it turns black at time 8 and is popped. Back to 4.
11	L6	v=4 fin[v]=9 time=9	4 has no unexplored neighbour left: it turns black at time 9 and is popped. Back to 3.
12	L6	v=3 fin[v]=10 time=10	3 has no unexplored neighbour left: it turns black at time 10 and is popped. Back to 1.
13	L6	v=1 fin[v]=11 time=11	1 has no unexplored neighbour left: it turns black at time 11 and is popped. Back to 0.
14	L6	u=0 fin[u]=12 time=12	0 finishes at time 12: all vertices reachable from it are black.
15	L6	return=[0, 1, 3, 2, 4, 5] tree edges=5 back edges=1	Preorder (discovery order): [0, 1, 3, 2, 4, 5]. 5 tree edges and 1 back edge; the numbers under each vertex are discovery/finish times, and the nesting of the intervals mirrors the DFS tree.

34.01.4

Forward and reverse edges

The **reverse graph** (or transpose) has every arrow flipped: a → b becomes b → a. Out-neighbours in the original are in-neighbours in the reverse, so the reverse answers *who points to me?* as quickly as the original answers *whom do I point to?*. Building it costs O(n + m).

Reversal turns reachability questions around: the vertices that can reach v in the original are exactly the vertices reachable from v in the reverse. It also appears in Kosaraju's SCC algorithm later in this chapter. The animation's *Ancestors* option searches the reversed arrows.

Java

1static List<List<Integer>> reverseGraph(List<List<Integer>> g) {
2    int n = g.size();
3    List<List<Integer>> rev = new ArrayList<>();
4    for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
5    for (int u = 0; u < n; u++)
6        for (int v : g.get(u)) rev.get(v).add(u);      // the arrow u -> v becomes v -> u
7    return rev;
8}

Directed graph facts: degrees, sources, sinks, descendants and ancestors

Interactive · edit the input

directed graph · 6 vertices · 6 edges

Arrow being read / vertex being expandedSource (in-degree 0)ReachedSink (out-degree 0)

in-degree

out-degree

Setup

Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.

Step 1 / 8

Java

1int[][] degrees(List<List<Integer>> g) {         // {in-degree, out-degree} per vertex
2    int n = g.size(); int[] in = new int[n], out = new int[n];
3    for (int u = 0; u < n; u++) for (int v : g.get(u)) { out[u]++; in[v]++; }
4    return new int[][]{in, out};                 // source: in == 0, sink: out == 0
5}
6List<Integer> descendants(List<List<Integer>> g, int s) {   // reached by one or more arrows
7    boolean[] seen = new boolean[g.size()];
8    Deque<Integer> stack = new ArrayDeque<>(g.get(s));
9    List<Integer> found = new ArrayList<>();
10    while (!stack.isEmpty()) {
11        int u = stack.pop();
12        if (seen[u]) continue;
13        seen[u] = true; found.add(u);
14        for (int v : g.get(u)) stack.push(v);
15    }
16    return found;                                // contains s only when s lies on a cycle
17}
18// ancestors(g, s) = descendants(reverse(g), s)

Live state

0 arrows read0 vertices reached

arrows

No condition evaluated on this step

Execution trace (dry run table)Show 8 steps

Step	Line	State	What happens
1	L2	n=6 arrows=6	Every vertex starts with in-degree 0 and out-degree 0. Each arrow a → b adds 1 to the out-degree of a and 1 to the in-degree of b.
2	L3	arrow=0 → 1 out[a]=1 in[b]=1	Arrow 0 → 1: out-degree of 0 is now 1, in-degree of 1 is now 1.
3	L3	arrow=0 → 2 out[a]=2 in[b]=1	Arrow 0 → 2: out-degree of 0 is now 2, in-degree of 2 is now 1.
4	L3	arrow=1 → 3 out[a]=1 in[b]=1	Arrow 1 → 3: out-degree of 1 is now 1, in-degree of 3 is now 1.
5	L3	arrow=2 → 3 out[a]=1 in[b]=2	Arrow 2 → 3: out-degree of 2 is now 1, in-degree of 3 is now 2.
6	L3	arrow=2 → 4 out[a]=2 in[b]=1	Arrow 2 → 4: out-degree of 2 is now 2, in-degree of 4 is now 1.
7	L3	arrow=3 → 5 out[a]=1 in[b]=1	Arrow 3 → 5: out-degree of 3 is now 1, in-degree of 5 is now 1.
8	L4	return=in [0, 1, 1, 2, 1, 1] out [2, 1, 2, 1, 0, 0] sources [0] sinks [4, 5]	Sources (in-degree 0): [0]. Sinks (out-degree 0): [4, 5]. The in-degrees add up to 6, the out-degrees to 6: both equal the 6 arrows.

Practice ladder

Now try it yourself

Easy

Find the Town Judge
Find Center of Star Graph

Medium

Find Eventual Safe States
Course Schedule

Advanced

Minimum Number of Vertices to Reach All Nodes
Count Visited Nodes in a Directed Graph

Key takeaways

Every arrow adds 1 to one out-degree and one in-degree; each list sums to the number of arrows.
Sources have in-degree 0 and sinks out-degree 0; a directed graph with no source contains a cycle.
A directed cycle, including a self-loop or a pair a to b and b to a, makes a graph not a DAG.
The reverse graph flips every arrow and turns 'who can I reach' into 'who can reach me'.