Graph AlgosGraph Algorithms

Connected Components

Partition an undirected graph into maximal groups of mutually reachable vertices with one traversal per group.

Learn Connected Components →
ABCDEFGHI
Stack
empty
1/15Scan nodes in order; each unlabeled node seeds a new component that a DFS floods. Two nodes share a label exactly when a path connects them.
Current nodeComponent 1, 4, …Component 2, 5, …Component 3, 6, …Traversal edge
PseudocodeLearn Connected Components →
1comp = {}; count = 0
2for s in nodes:
3  if s in comp: continue
4  count += 1; stack = [s]; comp[s] = count
5  while stack not empty:
6    u = stack.pop()
7    for v in neighbors(u):
8      if v not in comp: comp[v] = count; stack.push(v)
9return count
Complexity
best O(V + E)
avg O(V + E)
worst O(V + E)
space O(V)
Speed