Counting Connected Components
You'll learn: How to count the total number of separate "islands" in a graph by systematically visiting all vertices.
The Core Idea
Imagine a map with several isolated island groups. To count how many separate groups exist, you'd visit one island, explore its entire group, mark them all as visited, then look for the next unvisited island and repeat.
In graph terms, a connected component is a group of vertices that can reach each other through edges, but cannot reach vertices in other components. To count them, we iterate through all vertices in the graph. Each time we encounter an unvisited vertex, we've discovered a new component—we increment our counter and run a full DFS or BFS from that vertex to mark everything in its component as visited.
The Algorithm
- Initialize a
visitedarray to track which vertices you've seen - Set
componentCount = 0 - For each vertex
vin the graph:- If
vis not visited:- Increment
componentCount(found a new component!) - Run DFS or BFS starting from
vto mark all reachable vertices as visited
- Increment
- If
- Return
componentCount
The beauty is that DFS/BFS naturally explores one entire component before returning, so each traversal "consumes" exactly one component.
Why It Works
Every time you find an unvisited vertex, it must belong to a component you haven't explored yet (otherwise it would already be marked visited from a previous traversal). The subsequent DFS/BFS marks all vertices in that component, ensuring you never double-count.
Key Takeaway: Counting connected components requires iterating through all vertices and launching a DFS or BFS from each unvisited one—the number of launches equals the number of components.