Connected Components
Scenario
You have a map of islands and bridges. Some islands are connected by bridges, forming groups, but there's no way to travel between different groups.
How do you count exactly how many separate groups (or 'islands') exist in the entire network?
Why it exists
Problem: A standard BFS or DFS only explores nodes reachable from the starting point. If the graph is disconnected, nodes in other clusters will never be discovered.
Naive approach: Running a full BFS from every single node blindly would recount the same clusters repeatedly and waste time.
Better idea: Use a global `visited` set and an outer loop over all nodes. If a node is unvisited, it must belong to a brand-new component. Increment your count, run a traversal (BFS/DFS) to mark all nodes in that component as visited, and continue the loop.
Mental model
Scan the map. Every time you spot an unvisited piece of land, color it and all land connected to it. Count how many times you had to pick up a new color.
The algorithm pairs an outer loop with an inner traversal. The outer loop checks every node from `0` to `V-1`. If a node is unvisited, it's a new 'island'. The inner loop is just a standard BFS or DFS that shares the same global `visited` set. This marks the entire island. When the outer loop resumes, it safely skips all the newly marked nodes.
Repeated decision: is there any unvisited node left to start a fresh search from?
Explanation
Beyond routing, graph traversal is heavily used to categorize disconnected networks through Connected Component Analysis. A connected component is a maximal subset of vertices where a valid path exists between every pair of nodes, but no paths connect them to nodes outside the subset.
To find them, we combine an outer loop with an inner BFS or DFS:
- Create a global `visited` set.
- Loop through every node in the graph.
- If the node is *unvisited*, we have found a new component. Increment our component counter.
- Trigger a standard BFS or DFS starting from this node. As it runs, it adds every reachable node in this component to the global `visited` set.
- When the traversal finishes, the outer loop continues. It will skip over all nodes we just visited, ensuring we only launch a traversal exactly once per component.
Here is a hand-trace on a 5-node graph with 2 components:
```
Adjacency List:
0: [1]
1: [0, 2]
2: [1]
3: [4]
4: [3]
```
- Outer loop starts at `0`. Unvisited! `count = 1`.
- Inner BFS/DFS runs from `0`, visiting `0, 1, 2`. They are added to the `visited` set.
- Outer loop checks `1`. Already visited, skip.
- Outer loop checks `2`. Already visited, skip.
- Outer loop checks `3`. Unvisited! `count = 2`.
- Inner BFS/DFS runs from `3`, visiting `3, 4`.
- Outer loop checks `4`. Already visited, skip.
- Result: 2 components.
Despite the nested loops, this algorithm operates in strict `O(V+E)` time. The global `visited` set ensures the inner traversal executes exactly once per vertex across the *entire* graph.
Key points
- Dual-Loop Architecture: An outer loop iterates through all nodes; an inner loop performs BFS/DFS. The inner loop only fires when the outer loop hits an unvisited node.
- Global Visited Set: The `visited` set must be shared across all traversals. This guarantees each node is processed exactly once, preserving O(V+E) time.
Pattern: Connected Components
Recognition cues:
- counting groups, islands, or isolated networks
- image grid blob extraction
- checking if a graph is fully connected (count == 1)
Engineering examples
Image Processing (Blob Extraction)
Given a black-and-white image, identify distinct physical objects (blobs).
Treat the image grid as a graph where adjacent foreground pixels are connected. Connected-Component Labeling scans the matrix to isolate and count the blobs.
Common mistakes
- Resetting the visited set: If you clear the `visited` set between traversals, the algorithm degrades to `O(V * (V+E))` and you will drastically overcount components.
Recall questions
- What is the basic structure of a Connected Components algorithm?
- Why is the time complexity still O(V+E) despite having a loop inside a loop?
- What happens if a graph is completely connected (one piece) and you run this algorithm?
Questions & answers
Given an m x n 2D grid map of '1's (land) and '0's (water), return the number of islands.
Iterate over the grid. When a '1' is found, increment the island count and run a BFS/DFS to mark all connected '1's as visited so they aren't counted again.
Approach: This is the exact connected components algorithm applied to an implicit grid graph.
Find the number of connected components in an undirected graph given n nodes and an array of edges.
Build an adjacency list, then run the outer-loop + inner-DFS algorithm to count the unvisited starts.
Approach: Direct application of the algorithm on an explicit graph.
Continue learning
Previous: BFS on graphs
Previous: DFS on Graphs