Strongly Connected Component (Naive)

Naive algorithm for finding the Strongly Connected Component (SCC) from a single vertex. Performs forward DFS to find reachable vertices, then a separate backward DFS for each candidate. Introduction to more efficient algorithms (Kosaraju, Tarjan).

Sredni

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

Select programming language

Choose the language to see the naive SCC implementation.

Select example

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

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

Graph

1/0

Animation speed1.0x

Source codePython
1graph = {
2    0: [1],
3    1: [2],
4    2: [0, 3],
5    3: [4],
6    4: []
7}
8
9# === STEP 1: Who can I reach? (Forward DFS) ===
10
11my_house = 0
12
13who_i_can_reach = set()
14
15def dfs_who_i_can_reach(vertex):
16    who_i_can_reach.add(vertex)
17    for neighbor in graph[vertex]:
18        if neighbor not in who_i_can_reach:
19            dfs_who_i_can_reach(neighbor)
20
21# === STEP 2: Can they reach me? (DFS from each candidate) ===
22
23visited = set()
24
25def dfs_can_reach_my_house(vertex):
26    visited.add(vertex)
27    if vertex == my_house:
28        return True
29    for neighbor in graph[vertex]:
30        if neighbor not in visited:
31            did_neighbor_arrive = dfs_can_reach_my_house(neighbor)
32            if did_neighbor_arrive:
33                return True  # Neighbor found a path!
34    return False  # Nobody made it
35
36# === Running the algorithm ===
37
38dfs_who_i_can_reach(my_house)
39reachable = who_i_can_reach - {my_house}
40
41can_reach_me = set()
42for candidate in reachable:
43    visited.clear()
44    # Check if neighbor found a path
45    reached_my_house = dfs_can_reach_my_house(candidate)
46    if reached_my_house:
47        can_reach_me.add(candidate)
48
49# === Result: intersection of two sets ===
50my_scc = {my_house} | (reachable & can_reach_me)
51print(f"SCC({my_house}) = {my_scc}")

Variables0 variables

No variables at this step

1/0

Animation speed1.0x

1	graph = {
2	0: [1],
3	1: [2],
4	2: [0, 3],
5	3: [4],
6	4: []
7	}
8
9	# === STEP 1: Who can I reach? (Forward DFS) ===
10
11	my_house = 0
12
13	who_i_can_reach = set()
14
15	def dfs_who_i_can_reach(vertex):
16	who_i_can_reach.add(vertex)
17	for neighbor in graph[vertex]:
18	if neighbor not in who_i_can_reach:
19	dfs_who_i_can_reach(neighbor)
20
21	# === STEP 2: Can they reach me? (DFS from each candidate) ===
22
23	visited = set()
24
25	def dfs_can_reach_my_house(vertex):
26	visited.add(vertex)
27	if vertex == my_house:
28	return True
29	for neighbor in graph[vertex]:
30	if neighbor not in visited:
31	did_neighbor_arrive = dfs_can_reach_my_house(neighbor)
32	if did_neighbor_arrive:
33	return True # Neighbor found a path!
34	return False # Nobody made it
35
36	# === Running the algorithm ===
37
38	dfs_who_i_can_reach(my_house)
39	reachable = who_i_can_reach - {my_house}
40
41	can_reach_me = set()
42	for candidate in reachable:
43	visited.clear()
44	# Check if neighbor found a path
45	reached_my_house = dfs_can_reach_my_house(candidate)
46	if reached_my_house:
47	can_reach_me.add(candidate)
48
49	# === Result: intersection of two sets ===
50	my_scc = {my_house} \| (reachable & can_reach_me)
51	print(f"SCC({my_house}) = {my_scc}")