Kosaraju's Algorithm (all SCCs)

Kosaraju's algorithm finds ALL strongly connected components (SCC) in a directed graph using two DFS passes. The first pass records the finish order of vertices. The second pass processes vertices in reverse finish order on the reversed graph — each DFS in the second pass finds exactly one SCC!

Zaawansowany

O(V+E)O(V+E)OIJOI

Select programming language

Choose the language to see the Kosaraju SCC implementation.

Select example

Small, Medium, and Large examples show recursion code generation. Very large shows only the call stack.

Kosaraju SCC (Python): Small graph (5 vertices, directed)

Graph

1/0

Animation speed1.0x

Source codePython
1import sys
2sys.setrecursionlimit(1000000)
3
4graph = [
5    [1],        # 0,
6    [2],        # 1,
7    [0, 3],        # 2,
8    [4],        # 3,
9    [],        # 4
10]
11n = len(graph)
12
13reversed_graph = []
14for i in range(n):
15    reversed_graph.append([])
16
17for u in range(n):
18    for v in graph[u]:
19        reversed_graph[v].append(u)
20
21visited = [False] * n
22finish_stack = []
23
24def dfs_forward(vertex):
25    visited[vertex] = True
26    for neighbor in graph[vertex]:
27        if not visited[neighbor]:
28            dfs_forward(neighbor)
29    finish_stack.append(vertex)
30
31for v in range(n):
32    if not visited[v]:
33        dfs_forward(v)
34
35visited2 = [False] * n
36all_sccs = []
37
38def dfs_reversed(vertex, component):
39    visited2[vertex] = True
40    component.append(vertex)
41    for neighbor in reversed_graph[vertex]:
42        if not visited2[neighbor]:
43            dfs_reversed(neighbor, component)
44
45while finish_stack:
46    v = finish_stack.pop()
47    if not visited2[v]:
48        component = []
49        dfs_reversed(v, component)
50        all_sccs.append(component)
51
52for i, scc in enumerate(all_sccs):
53    print(f"SCC {i+1}: {scc}")

Variables0 variables

No variables at this step

1/0

Animation speed1.0x

1	import sys
2	sys.setrecursionlimit(1000000)
3
4	graph = [
5	[1], # 0,
6	[2], # 1,
7	[0, 3], # 2,
8	[4], # 3,
9	[], # 4
10	]
11	n = len(graph)
12
13	reversed_graph = []
14	for i in range(n):
15	reversed_graph.append([])
16
17	for u in range(n):
18	for v in graph[u]:
19	reversed_graph[v].append(u)
20
21	visited = [False] * n
22	finish_stack = []
23
24	def dfs_forward(vertex):
25	visited[vertex] = True
26	for neighbor in graph[vertex]:
27	if not visited[neighbor]:
28	dfs_forward(neighbor)
29	finish_stack.append(vertex)
30
31	for v in range(n):
32	if not visited[v]:
33	dfs_forward(v)
34
35	visited2 = [False] * n
36	all_sccs = []
37
38	def dfs_reversed(vertex, component):
39	visited2[vertex] = True
40	component.append(vertex)
41	for neighbor in reversed_graph[vertex]:
42	if not visited2[neighbor]:
43	dfs_reversed(neighbor, component)
44
45	while finish_stack:
46	v = finish_stack.pop()
47	if not visited2[v]:
48	component = []
49	dfs_reversed(v, component)
50	all_sccs.append(component)
51
52	for i, scc in enumerate(all_sccs):
53	print(f"SCC {i+1}: {scc}")