Connected Components in Undirected Graphs
What You'll Learn
You'll learn what connected components are and why they help us analyze the structure of undirected graphs.
The Core Idea
A connected component is a maximal subgraph where every vertex can reach every other vertex through some path. "Maximal" means you can't add any more vertices to it while keeping this property—it's as large as possible.
Think of it like islands in an archipelago. Each island represents a connected component: you can walk anywhere within that island, but you can't reach another island without a boat. The entire archipelago is the graph, and each island is a separate connected component.
In an undirected graph, connected components partition the vertices into distinct groups. Every vertex belongs to exactly one component, and within that component, there's a path between any two vertices.
Why This Matters
Connected components reveal the "clustering" of a graph:
- A graph with one component is fully connected—there's a path between any two vertices
- Multiple components mean the graph is disconnected—some vertices are unreachable from others
Using BFS or DFS (which you've already learned), you can identify all connected components by visiting unvisited vertices and marking everything reachable from each starting point.
Example
Consider vertices: A-B-C and D-E (two separate groups with no edges between them). This graph has two connected components:
- Component 1: {A, B, C} — any vertex here can reach the others
- Component 2: {D, E} — these are connected to each other but isolated from A, B, C
Key Takeaway: Connected components are maximal subgraphs where all vertices are mutually reachable, partitioning an undirected graph into distinct "islands" of connectivity.