34.05Intermediate / Advanced4 topics14 min4 interactive animations

Directed reachability

Reachability in a directed graph is asymmetric: ancestors reach a vertex, descendants are reached from it, the transitive closure records every pair, and reversing the graph answers the ancestor questions with one search.

Learning goals

Define ancestors and descendants and compute each with one search
Build the transitive closure of a DAG in reverse topological order
Answer a question about many targets with one search of the reversed graph

Prerequisites

Graph reachabilityTopological sort

Which modules does this one depend on, directly or not? Which others are affected if it changes? Which states can still reach a safe end? These questions all ask for the set of vertices on one side of a path.

34.05.1

Ancestor queries

An **ancestor** of v is a vertex that has a path to v. To list the ancestors of every vertex of a DAG, run one reverse search per vertex, or propagate sets along a topological order. Ancestors of v are its direct predecessors plus all of *their* ancestors.

The answers can be large (up to n(n - 1) / 2 pairs in total), so building them all costs O(n(n + m)) time and O(n^2) space. For a single vertex one search is enough. Choose *Ancestors of a vertex* in the animation.

Java

1static List<List<Integer>> allAncestors(int n, int[][] edges) {   // edges {u, v}: ancestors.get(v) lists the vertices with a path to v
2    List<List<Integer>> rev = new ArrayList<>();
3    for (int i = 0; i < n; i++) rev.add(new ArrayList<>());
4    for (int[] e : edges) rev.get(e[1]).add(e[0]);
5    List<List<Integer>> result = new ArrayList<>();
6    for (int v = 0; v < n; v++) {
7        boolean[] seen = new boolean[n];
8        Deque<Integer> stack = new ArrayDeque<>(rev.get(v));
9        while (!stack.isEmpty()) {
10            int u = stack.pop();
11            if (seen[u]) continue;
12            seen[u] = true;
13            for (int p : rev.get(u)) stack.push(p);
14        }
15        List<Integer> list = new ArrayList<>();
16        for (int u = 0; u < n; u++) if (seen[u]) list.add(u);
17        result.add(list);
18    }
19    return result;
20}

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.05.2

Descendants

A **descendant** of v is a vertex reachable from v by one or more arrows. One DFS or BFS from v finds them all. In a graph with cycles, v can be its own descendant (if it lies on a cycle); in a DAG it never is, which is another test for acyclicity.

Descendants are what a change affects: the modules to rebuild, the cells to recompute. The animation's second option, *Descendants of a vertex*, includes a preset where the start vertex ends up in its own list.

Java

1static List<Integer> descendantSet(List<List<Integer>> g, int s) {   // reached by one or more arrows, in increasing order
2    boolean[] seen = new boolean[g.size()];
3    Deque<Integer> stack = new ArrayDeque<>(g.get(s));
4    while (!stack.isEmpty()) {
5        int u = stack.pop();
6        if (seen[u]) continue;
7        seen[u] = true;
8        for (int v : g.get(u)) stack.push(v);
9    }
10    List<Integer> out = new ArrayList<>();
11    for (int v = 0; v < g.size(); v++) if (seen[v]) out.add(v);       // contains s only when s lies on a cycle
12    return out;
13}

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.05.3

Transitive closure

The **transitive closure** lists every pair (u, v) where v is reachable from u. On a DAG it can be built without any search per vertex: process vertices in *reverse* topological order and set reach[u] = {u} united with reach[v] for every arrow u → v. Each reach[v] is complete before u needs it.

Storing each set as a bitset makes every union a handful of word operations. The animation for graph reachability shows the closure by Warshall's algorithm, which also works when the graph has cycles.

Java

1static BitSet[] dagClosure(List<List<Integer>> g) {              // reach[u] holds every vertex reachable from u, u included; g must be a DAG
2    int n = g.size();
3    int[] indeg = new int[n], order = new int[n];
4    for (List<Integer> out : g) for (int v : out) indeg[v]++;
5    Deque<Integer> q = new ArrayDeque<>();
6    for (int v = 0; v < n; v++) if (indeg[v] == 0) q.add(v);
7    int k = 0;
8    while (!q.isEmpty()) {
9        int u = q.poll();
10        order[k++] = u;
11        for (int v : g.get(u)) if (--indeg[v] == 0) q.add(v);
12    }
13    BitSet[] reach = new BitSet[n];
14    for (int i = n - 1; i >= 0; i--) {                           // reverse topological order: successors are finished first
15        int u = order[i];
16        reach[u] = new BitSet(n);
17        reach[u].set(u);
18        for (int v : g.get(u)) reach[u].or(reach[v]);
19    }
20    return reach;
21}

Reachability: path existence, reversed search, transitive closure

Interactive · edit the input

directed graph · 6 vertices · 5 edges

Being expandedReaches the targetNewly reachableVisitedReachable

stack

Setup

Is there a path from 0 to 3? Search from 0 and stop as soon as 3 is reached. Arrows can only be followed forwards.

Step 1 / 6

Java

1boolean reachable(List<List<Integer>> g, int s, int t) {
2    boolean[] seen = new boolean[g.size()];
3    Deque<Integer> stack = new ArrayDeque<>(); stack.push(s); seen[s] = true;
4    while (!stack.isEmpty()) {
5        int u = stack.pop();
6        if (u == t) return true;
7        for (int v : g.get(u)) if (!seen[v]) { seen[v] = true; stack.push(v); }
8    }
9    return false;
10}
11boolean[] canReach(List<List<Integer>> reversed, int t) {      // search from t along reversed edges
12    boolean[] seen = new boolean[reversed.size()];
13    Deque<Integer> q = new ArrayDeque<>(); q.add(t); seen[t] = true;
14    while (!q.isEmpty()) { int u = q.poll(); for (int v : reversed.get(u)) if (!seen[v]) { seen[v] = true; q.add(v); } }
15    return seen;
16}
17boolean[][] closure(boolean[][] adj) {           // Warshall: reach[i][j] using intermediate vertices 0..k
18    int n = adj.length; boolean[][] r = new boolean[n][];
19    for (int i = 0; i < n; i++) { r[i] = adj[i].clone(); r[i][i] = true; }
20    for (int k = 0; k < n; k++)
21        for (int i = 0; i < n; i++)
22            if (r[i][k]) for (int j = 0; j < n; j++) r[i][j] |= r[k][j];
23    return r;
24}

Live state

0 vertices visited

No condition evaluated on this step

Execution trace (dry run table)Show 6 steps

Step	Line	State	What happens
1	L3	s=0 t=3	Is there a path from 0 to 3? Search from 0 and stop as soon as 3 is reached. Arrows can only be followed forwards.
2	L7	u=0 pushed=[1, 4]	Pop 0: push the unvisited out-neighbours 1, 4.
3	L7	u=4 pushed=none	Pop 4: no unvisited out-neighbour.
4	L7	u=1 pushed=[2]	Pop 1: push the unvisited out-neighbours 2.
5	L7	u=2 pushed=[3]	Pop 2: push the unvisited out-neighbours 3.
6	L6	return=true	3 reached: a path from 0 exists.

34.05.4

Reversed DAG

To find all vertices that can reach *any* of several targets, do not search from each vertex. Reverse the graph and start one search from all the targets together; everything it reaches is a vertex with a path to a target. The cost is one O(n + m) search.

This solves "which states are safe?" problems (a state is safe if every path leads to a terminal), and "which vertices can influence this set?". It is the multi-source form of the reversed-reachability idea from the previous chapter.

Java

1static boolean[] canReachTargets(List<List<Integer>> g, int[] targets) {   // true for every vertex with a path to some target
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++) for (int v : g.get(u)) rev.get(v).add(u);
6    boolean[] can = new boolean[n];
7    Deque<Integer> stack = new ArrayDeque<>();
8    for (int t : targets) if (!can[t]) { can[t] = true; stack.push(t); }
9    while (!stack.isEmpty()) {
10        int u = stack.pop();
11        for (int p : rev.get(u)) if (!can[p]) { can[p] = true; stack.push(p); }
12    }
13    return can;
14}

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 if Path Exists in Graph

Medium

All Ancestors of a Node in a Directed Acyclic Graph
Find Eventual Safe States
Course Schedule IV

Advanced

Minimum Number of Vertices to Reach All Nodes

Key takeaways

Ancestors reach a vertex; descendants are reached from it; both come from one search, the second on the reversed graph.
A vertex is its own descendant only when it lies on a cycle.
On a DAG, build the closure in reverse topological order with bitsets.
Search the reversed graph from all targets at once to find everything that can reach them.