Connected components
In an undirected graph a connected component is a maximal group of vertices where every pair is linked by some path. A graph may split into several components, like separate islands with no bridges between them. Counting and labeling components answers questions like how many isolated clusters exist in a network.
Sweep and flood
The method is a simple sweep combined with a traversal.
- Keep a count starting at zero and a visited marker for every vertex.
- Walk through all vertices in any order.
- When you reach an unvisited vertex, increase the count and run a BFS or DFS that marks the whole component reachable from it.
- Vertices reached by that traversal are skipped later because they are now visited.
Each traversal claims one entire island, so the count equals the number of components.
Union find alternative
For graphs that arrive as a stream of edges, a union find or disjoint set structure can merge endpoints as edges appear and report the component count without a full traversal. Both approaches run in nearly linear time.
Key idea
Sweep every vertex and launch a traversal from each unvisited one, so the number of launches equals the number of connected components.