DSA Tracker

Visualize

Number of Connected Components in an Undirected Graph

BFS from every unvisited vertex: one fresh run per component

time O(V + E)space O(V + E)

A component is just 'everything reachable from here.' So the algorithm never has to look for components directly — it only has to make sure every vertex gets visited once. Walk the vertices in order; whenever one has not been visited yet, that is proof it belongs to a group nobody has explored, so start a fresh BFS from it and count one more component. A vertex with zero edges is not a special case — its BFS just queues nothing, and it still counts as a component of size one. The badge on each vertex is the component number it was assigned; the side panel is the BFS queue for whichever component is currently being explored.

Details

Animated on: 6 vertices (0..5) with undirected edges 0-1, 2-3, 3-4 — vertex 5 has no edge. How many connected components does the graph have?

Problem:Number of Connected Components in an Undirected GraphMedium

BFS from every unvisited vertex: one fresh run per component

step 1 / 14

Undirected graph, no component labels yet

6 vertices and 3 undirected edges. Vertex 5 does not appear in any edge at all — it is still its own component. The only way to find every group is to walk from each unvisited vertex and see how far it reaches.

Pseudocode
1FUNCTION countComponents(n, edges):
2  BUILD adj FROM edges
3  visited <- ARRAY OF n FALSE
4  count <- 0
5  FOR s FROM 0 TO n - 1
6    IF visited[s] CONTINUE
7    count <- count + 1
8    queue <- [s]
9    visited[s] <- true
10    WHILE queue NOT EMPTY
11      u <- REMOVE FIRST FROM queue
12      FOR EACH v IN adj[u]
13        IF NOT visited[v]: visited[v] <- true; APPEND v TO queue
14  RETURN count

← / → step · space play · Home restart

Every step in words

Show all 14 steps
  1. 6 vertices and 3 undirected edges. Vertex 5 does not appear in any edge at all — it is still its own component. The only way to find every group is to walk from each unvisited vertex and see how far it reaches.
  2. 0 has not been visited, so it starts component #1. Queue it and mark it visited.
  3. Pop 0. Neighbour 1 — 1 is unvisited, so mark it as component #1 and queue it.
  4. Pop 1. Neighbour 0 is already visited — nothing new to queue.
  5. The queue is empty — component #1 is exactly {0, 1}.
  6. 2 has not been visited, so it starts component #2. Queue it and mark it visited.
  7. Pop 2. Neighbour 3 — 3 is unvisited, so mark it as component #2 and queue it.
  8. Pop 3. Neighbours 2, 4 — 4 is unvisited, so mark it as component #2 and queue it.
  9. Pop 4. Neighbour 3 is already visited — nothing new to queue.
  10. The queue is empty — component #2 is exactly {2, 3, 4}.
  11. 5 has not been visited, and it has no edges at all — it still starts component #3, all by itself.
  12. Pop 5. It has no neighbours to explore — the queue empties immediately.
  13. The queue is empty — component #3 is exactly {5}.
  14. Every vertex is visited and 3 separate BFS runs were needed to cover them all. RETURN 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Number of Connected Components in an Undirected Graph in the editorAll Graph problemsBack to roadmap