Course contentsShow
← Computer Science
Lesson 730 of 2,87217. Graph Traversal AlgorithmsFree lesson

Component Finding with DFS

Use depth-first search to identify all vertices in a single connected component by exploring from a start vertex.

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

  1. Choose a starting vertex in the component you want to explore
  2. Run DFS from that vertex (recursive or iterative)
  3. Mark each visited vertex as you explore
  4. 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.