Connected Components

Algorithm for finding connected components in an undirected graph. Uses DFS with an outer loop over all vertices — each unvisited vertex starts a new component, and DFS visits all vertices in that component.

Sredni

O(V+E)O(V)OIJOI

Select programming language

Choose the language to see the connected components implementation.

Select example

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

Connected Components (Python): Small graph (5 vertices, undirected)

Graph

1/0

Animation speed1.0x

Source codePython
1graph = {
2    1: [2, 3],
3    2: [1],
4    3: [1],
5    4: [5],
6    5: [4]
7}
8visited = set()
9component = [0] * (len(graph) + 1)
10component_id = 0
11
12def dfs(vertex, nr):
13    """Assigns vertex to component nr."""
14    visited.add(vertex)
15    component[vertex] = nr
16
17    for neighbor in graph[vertex]:
18        if neighbor not in visited:
19            dfs(neighbor, nr)
20
21# Outer loop — key to the algorithm
22for w in graph:
23    if w not in visited:
24        component_id += 1
25        dfs(w, component_id)
26print(f"Components: {component}")

Variables0 variables

No variables at this step

1/0

Animation speed1.0x

1	graph = {
2	1: [2, 3],
3	2: [1],
4	3: [1],
5	4: [5],
6	5: [4]
7	}
8	visited = set()
9	component = [0] * (len(graph) + 1)
10	component_id = 0
11
12	def dfs(vertex, nr):
13	"""Assigns vertex to component nr."""
14	visited.add(vertex)
15	component[vertex] = nr
16
17	for neighbor in graph[vertex]:
18	if neighbor not in visited:
19	dfs(neighbor, nr)
20
21	# Outer loop — key to the algorithm
22	for w in graph:
23	if w not in visited:
24	component_id += 1
25	dfs(w, component_id)
26	print(f"Components: {component}")