Pattern visualizer
Number of Connected Components in Undirected Graph
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. 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?.
BFS from every unvisited vertex: one fresh run per component
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.
1FUNCTION countComponents(n, edges):2 BUILD adj FROM edges3 visited <- ARRAY OF n FALSE4 count <- 05 FOR s FROM 0 TO n - 16 IF visited[s] CONTINUE7 count <- count + 18 queue <- [s]9 visited[s] <- true10 WHILE queue NOT EMPTY11 u <- REMOVE FIRST FROM queue12 FOR EACH v IN adj[u]13 IF NOT visited[v]: visited[v] <- true; APPEND v TO queue14 RETURN count
← / → step · space play · Home restart