Connected components

O(V + E)

A connected component is a maximal set of vertices that can all reach one another by following edges; a graph splits into one or more disjoint components. To find them, pick any unvisited vertex and flood-fill outward with BFS (or DFS), giving every reachable vertex the same colour — that's one component. Repeat from the next unvisited vertex with a new colour until none remain. The whole sweep touches each vertex and edge once, so it runs in O(V + E). It answers "is the graph in one piece?" and underlies clustering, maze solving, and network reachability.

Click empty space = vertex · click two vertices = edge · drag = moveStart: A
Input graph
Edit the input and press Play

How it works

  1. Pick an unvisited vertex and start a new component colour.
  2. Flood outward (BFS/DFS), painting every reachable vertex that colour.
  3. When the flood stops, that component is complete.
  4. Move to the next unvisited vertex with a fresh colour until all are painted.

Pseudocode

1connectedComponents(graph):         # O(V + E)2  k ← 03  for each vertex s:4    if s is unvisited:5      BFS/DFS from s, tagging every6      reachable vertex with colour k  # one component7      k ← k + 18  return k                            # number of components