Component Finding with DFS
What you'll learn: How to use depth-first search to discover all vertices belonging to a single connected component in a graph.
The Core Idea
When you perform a DFS starting from any vertex, the search will naturally visit every vertex reachable from that starting point—and only those vertices. This makes DFS perfect for identifying all members of a connected component.
Think of it like exploring a network of caves: when you start from one entrance and explore every tunnel you can reach (the DFS principle), you'll map out one complete cave system. Any cave you can't reach from your starting point must belong to a different, disconnected system.
How It Works
- Choose a starting vertex in the component you want to explore
- Run DFS from that vertex (recursive or iterative)
- Mark each visited vertex as you explore
- When DFS completes, all marked vertices form one complete connected component
The beauty is that DFS guarantees you won't "leak" into other components—if there's no edge connecting two parts of the graph, DFS simply can't jump between them.
Why This Matters
This technique is fundamental for:
- Breaking a graph into its natural "clusters"
- Determining if two vertices are in the same component
- Counting the total number of components (run DFS repeatedly from unvisited vertices)
- Social network analysis (finding isolated groups)
Key Takeaway: A single DFS traversal from a start vertex will visit exactly all vertices in that vertex's connected component, making DFS a natural and efficient tool for component identification.