Introduction
Donald B. Johnson's algorithm (1975) finds all elementary cycles (simple circuits) in a directed graph. It is one of the most efficient algorithms for this problem, running in O((n + e)(c + 1)) time where n is vertices, e is edges, and c is the number of cycles found. The key insight is a "blocking" mechanism that prevents redundant exploration — once a node is known not to lead to a cycle through the current start vertex, it is blocked and skipped until it is unblocked by finding a new cycle. Understanding the pseudocode requires grasping three concepts: the DFS-based circuit search, the blocking/unblocking mechanism, and the SCC-based decomposition.
High-Level Algorithm Structure
1JOHNSON(G):
2 // Find all elementary circuits in directed graph G
3 s = 1 // Start vertex (processes vertices in order)
4 while s < n:
5 // Build subgraph of G induced by vertices {s, s+1, ..., n}
6 Gsub = subgraph(G, {s, ..., n})
7
8 // Find strongly connected components (SCCs)
9 SCCs = TARJAN(Gsub)
10
11 // Find the SCC containing the smallest vertex
12 SCC_s = SCC containing vertex s (if any)
13
14 if SCC_s exists:
15 // Initialize blocking structures
16 for each v in SCC_s:
17 blocked[v] = false
18 B[v] = {} // Empty set
19
20 CIRCUIT(s, s, SCC_s)
21
22 s = s + 1
The algorithm processes each vertex as a potential starting point for cycles. It first finds the strongly connected component containing that vertex (cycles can only exist within SCCs), then searches for all cycles starting and ending at that vertex.
The CIRCUIT Function (Core DFS)
1CIRCUIT(v, s, graph):
2 // v = current vertex, s = start vertex
3 f = false // Did we find a cycle through v?
4 stack.push(v)
5 blocked[v] = true
6
7 for each w in adjacency[v]:
8 if w == s:
9 // Found a cycle! Output stack contents
10 OUTPUT(stack + [s])
11 f = true
12 else if not blocked[w]:
13 if CIRCUIT(w, s, graph):
14 f = true
15
16 if f:
17 UNBLOCK(v) // Cycle found: unblock v for future searches
18 else:
19 // No cycle found through v
20 for each w in adjacency[v]:
21 if v not in B[w]:
22 B[w].add(v) // Remember: if w is unblocked, unblock v too
23
24 stack.pop()
25 return f
This is a depth-first search from vertex v looking for paths back to s. When the search reaches s, a cycle is found. The return value f indicates whether any cycle was found through v.
The UNBLOCK Function
1UNBLOCK(u):
2 blocked[u] = false
3 for each w in B[u]:
4 if blocked[w]:
5 UNBLOCK(w) // Recursively unblock dependencies
6 B[u] = {} // Clear the dependency set
When a cycle is found through vertex u, we unblock it. The set B[u] tracks vertices that should also be unblocked when u is unblocked — this cascading unblock is what makes the algorithm efficient.
Python Implementation
1from collections import defaultdict
2
3def johnsons_algorithm(graph):
4 """Find all elementary cycles in a directed graph."""
5 def strong_connect(v, index_counter, stack, lowlinks, index, on_stack, sccs):
6 index[v] = index_counter[0]
7 lowlinks[v] = index_counter[0]
8 index_counter[0] += 1
9 stack.append(v)
10 on_stack[v] = True
11
12 for w in graph.get(v, []):
13 if w not in index:
14 strong_connect(w, index_counter, stack, lowlinks, index, on_stack, sccs)
15 lowlinks[v] = min(lowlinks[v], lowlinks[w])
16 elif on_stack.get(w, False):
17 lowlinks[v] = min(lowlinks[v], index[w])
18
19 if lowlinks[v] == index[v]:
20 scc = []
21 while True:
22 w = stack.pop()
23 on_stack[w] = False
24 scc.append(w)
25 if w == v:
26 break
27 if len(scc) > 1 or (len(scc) == 1 and v in graph.get(v, [])):
28 sccs.append(scc)
29
30 def find_sccs(subgraph, vertices):
31 sccs = []
32 index = {}
33 lowlinks = {}
34 on_stack = {}
35 stack = []
36 index_counter = [0]
37 for v in vertices:
38 if v not in index:
39 strong_connect(v, index_counter, stack, lowlinks, index, on_stack, sccs)
40 return sccs
41
42 def circuit(v, s, adj, blocked, B, stack, cycles):
43 f = False
44 stack.append(v)
45 blocked[v] = True
46
47 for w in adj.get(v, []):
48 if w == s:
49 cycles.append(list(stack))
50 f = True
51 elif not blocked.get(w, False):
52 if circuit(w, s, adj, blocked, B, stack, cycles):
53 f = True
54
55 if f:
56 unblock(v, blocked, B)
57 else:
58 for w in adj.get(v, []):
59 if v not in B[w]:
60 B[w].add(v)
61
62 stack.pop()
63 return f
64
65 def unblock(u, blocked, B):
66 blocked[u] = False
67 for w in list(B[u]):
68 if blocked.get(w, False):
69 unblock(w, blocked, B)
70 B[u] = set()
71
72 vertices = sorted(graph.keys())
73 cycles = []
74
75 for s in vertices:
76 subgraph_vertices = [v for v in vertices if v >= s]
77 sub_adj = {v: [w for w in graph.get(v, []) if w >= s]
78 for v in subgraph_vertices}
79
80 sccs = find_sccs(sub_adj, subgraph_vertices)
81 scc_with_s = None
82 for scc in sccs:
83 if s in scc:
84 scc_with_s = set(scc)
85 break
86
87 if scc_with_s:
88 adj = {v: [w for w in sub_adj.get(v, []) if w in scc_with_s]
89 for v in scc_with_s}
90 blocked = {}
91 B = defaultdict(set)
92 stack = []
93 for v in scc_with_s:
94 blocked[v] = False
95 circuit(s, s, adj, blocked, B, stack, cycles)
96
97 return cycles
98
99# Usage
100graph = {
101 1: [2],
102 2: [3],
103 3: [1, 4],
104 4: [2]
105}
106
107cycles = johnsons_algorithm(graph)
108for c in cycles:
109 print(c)
110# [1, 2, 3]
111# [2, 3, 4]
Blocking Mechanism Explained
1Step-by-step for graph: 1→2→3→1, 2→3→4→2
2
3Starting at s=1:
4 CIRCUIT(1, 1):
5 blocked[1] = true, stack = [1]
6 Visit 2:
7 CIRCUIT(2, 1):
8 blocked[2] = true, stack = [1, 2]
9 Visit 3:
10 CIRCUIT(3, 1):
11 blocked[3] = true, stack = [1, 2, 3]
12 Visit 1: w == s → CYCLE FOUND [1, 2, 3] ✓
13 Visit 4: CIRCUIT(4, 1)
14 blocked[4] = true, stack = [1, 2, 3, 4]
15 Visit 2: blocked → skip
16 No cycle → B[2].add(4)
17 stack = [1, 2, 3]
18 f = true → UNBLOCK(3)
19 f = true → UNBLOCK(2) → cascades to UNBLOCK(4)
20 f = true → UNBLOCK(1)
21
22Starting at s=2:
23 Subgraph: {2, 3, 4}
24 Finds cycle [2, 3, 4] ✓
The blocking mechanism prevents revisiting vertex 4 from vertex 2 when searching for cycles through vertex 1 (since 4 cannot lead back to 1). But when a cycle is found through 3, the unblock cascades to 4 via B[2], allowing future exploration.
Common Pitfalls
Confusing blocking with visited: Blocking is not the same as a standard DFS visited flag. Blocked nodes can be unblocked later when new cycles are discovered. A visited flag in standard DFS is permanent; blocking in Johnson's algorithm is temporary and cycle-dependent.
Not restricting to the SCC subgraph: The circuit search must only traverse edges within the strongly connected component containing s. Searching the full graph finds paths that cannot form cycles, wasting time and producing incorrect results.
Forgetting the cascading unblock via B sets: The B[w] sets record dependencies: "when w is unblocked, also unblock vertices in B[w]." Skipping this cascade causes the algorithm to miss cycles because vertices remain incorrectly blocked.
Not processing vertices in order: The algorithm requires processing start vertices in ascending order and restricting the subgraph to vertices >= s. This prevents finding the same cycle multiple times (once from each vertex in the cycle).
Self-loops as special case: A self-loop (vertex with an edge to itself) is an elementary cycle of length 1. The SCC detection must include single-vertex SCCs that have self-loops. Many SCC implementations skip single-vertex components, causing self-loops to be missed.
Summary
Johnson's algorithm finds all elementary cycles in a directed graph in O((n + e)(c + 1)) time
It processes each vertex as a starting point and searches for cycles within its SCC
The blocking mechanism prevents redundant exploration: blocked vertices are skipped until new cycles make re-exploration worthwhile
The B sets enable cascading unblock: when a cycle is found, all dependent vertices are unblocked recursively
The algorithm restricts search to vertices >= the current start vertex to avoid finding duplicate cycles
Use Tarjan's algorithm to find SCCs as a preprocessing step for each iteration
