33.06Intermediate / Advanced4 topics15 min4 interactive animations

Graph reachability

Reachability asks whether a path exists from one vertex to another; one search answers it for a single pair, searching the reversed graph answers who can reach a target, and Warshall's algorithm tabulates all pairs.

Learning goals

Decide whether a path exists in a directed or undirected graph
Explain the transitive closure and compute it by repeated searches
Find everything that can reach a target by reversing the arrows
Fill a reachability matrix with Warshall's algorithm

Prerequisites

Depth-first searchBreadth-first search

Can data flow from this service to that one? Can a user reach a page by following links? Does one task depend, directly or indirectly, on another? All are reachability questions.

33.06.1

Path existence

To test whether t is reachable from s, search from s and see whether t is ever visited. You can stop as soon as t is found. In a directed graph reachability is not symmetric: a path from s to t says nothing about one from t to s.

The animation's first option shows both outcomes: the *Path exists* preset reaches the target, and the second preset flips the direction so the answer is no.

Java

1static boolean hasPath(List<List<Integer>> g, int s, int t) {    // directed reachability by DFS with a stack
2    boolean[] seen = new boolean[g.size()];
3    Deque<Integer> stack = new ArrayDeque<>();
4    seen[s] = true;
5    stack.push(s);
6    while (!stack.isEmpty()) {
7        int u = stack.pop();
8        if (u == t) return true;
9        for (int v : g.get(u))
10            if (!seen[v]) { seen[v] = true; stack.push(v); }
11    }
12    return false;
13}

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.

33.06.2

Transitive closure concept

The **transitive closure** of a graph has an edge u -> v whenever the original has a path from u to v (of any length, here including length 0). Said differently, it is the reachability relation written as a graph. One way to build it is to search from every vertex: n searches of O(n + m) each, O(n(n + m)) in total.

That is fast for sparse graphs. For dense graphs the matrix method in the last item is simpler and has the same O(n^3) worst case. The closure is useful when you need many reachability queries and can afford n^2 bits of memory.

Java

1static boolean[][] closureBySearch(List<List<Integer>> g) {       // reach[u][v] = true when v is reachable from u
2    int n = g.size();
3    boolean[][] reach = new boolean[n][n];
4    for (int s = 0; s < n; s++) {
5        Deque<Integer> stack = new ArrayDeque<>();
6        reach[s][s] = true;                                       // a vertex reaches itself with an empty path
7        stack.push(s);
8        while (!stack.isEmpty()) {
9            int u = stack.pop();
10            for (int v : g.get(u))
11                if (!reach[s][v]) { reach[s][v] = true; stack.push(v); }
12        }
13    }
14    return reach;
15}

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.

33.06.3

Reverse graph reachability

To find every vertex that can reach t, do not search from each vertex. Reverse every arrow and search once from t: a vertex is found exactly when the original graph has a path from it to t. One O(n + m) search replaces n searches.

The same trick finds the vertices that can reach a set of targets, such as safe states in a game or the callers of a function. Choose *Who can reach t? Search the reversed graph* in the animation.

Java

1static boolean[] canReachTarget(List<List<Integer>> g, int t) {   // canReach[v] = true if v has a path to t
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);                 // flip each arrow
7    boolean[] canReach = new boolean[n];
8    Deque<Integer> stack = new ArrayDeque<>();
9    canReach[t] = true;
10    stack.push(t);
11    while (!stack.isEmpty()) {
12        int u = stack.pop();
13        for (int v : rev.get(u))
14            if (!canReach[v]) { canReach[v] = true; stack.push(v); }
15    }
16    return canReach;
17}

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.

33.06.4

Reachability matrix

Warshall's algorithm fills the closure matrix directly. Start with reach[i][j] = adj[i][j] and reach[i][i] = true. For each intermediate vertex k in turn, allow paths through k: if i reaches k and k reaches j, then i reaches j. After all n values of k, the matrix is the transitive closure.

The loop order matters: k must be the outermost loop. Time is O(n^3) and space O(n^2); with bitsets for the rows each inner loop becomes a word-wise OR. Pick the *Transitive closure (Warshall)* option to watch the matrix fill.

Java

1static boolean[][] warshall(boolean[][] adj) {                    // adj[i][j] = an arrow i -> j
2    int n = adj.length;
3    boolean[][] reach = new boolean[n][];
4    for (int i = 0; i < n; i++) { reach[i] = adj[i].clone(); reach[i][i] = true; }
5    for (int k = 0; k < n; k++)                                   // the allowed intermediate vertices 0..k
6        for (int i = 0; i < n; i++)
7            if (reach[i][k])
8                for (int j = 0; j < n; j++)
9                    if (reach[k][j]) reach[i][j] = true;
10    return reach;
11}

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.

Practice ladder

Now try it yourself

Easy

Find if Path Exists in Graph

Medium

All Paths From Source to Target
Course Schedule
Keys and Rooms

Advanced

Course Schedule IV
Find Eventual Safe States

Key takeaways

One search answers a single reachability query in O(n + m); directed reachability is not symmetric.
The transitive closure lists every reachable pair; n searches or Warshall build it.
Search the reversed graph once to find everything that can reach a target.
In Warshall's algorithm the intermediate vertex k is the outermost loop.