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

Component Finding with BFS

Apply breadth-first search as an alternative to DFS for discovering all vertices within one connected component.

Component Finding with BFS

You'll learn how to discover all vertices in a connected component using breadth-first search instead of depth-first search.

The Core Idea

You already know that BFS explores a graph level-by-level, visiting all neighbors before moving outward. Just like DFS, BFS can find all vertices reachable from a starting point—which is exactly what defines a connected component. The only difference is the order of exploration, not the completeness of the search.

When you run BFS from an unvisited vertex, it fans out like ripples in a pond, marking every vertex it touches. All those marked vertices belong to the same component. Repeat this process for any remaining unvisited vertices to find all components.

Why Use BFS for Components?

While DFS is more common for component finding (simpler recursion), BFS offers advantages:

  • Level structure: You get vertices organized by distance from the start
  • Shortest paths: BFS naturally finds shortest paths while discovering the component
  • Iterative control: Easier to manage memory in graphs that might cause deep recursion

The Process

  1. Mark all vertices as unvisited
  2. For each unvisited vertex:
    • Start a BFS from that vertex
    • All vertices reached belong to one component
    • Increment the component count
  3. Continue until all vertices are visited

Think of it like exploring islands: BFS swims systematically outward from shore, visiting nearby land first, then farther beaches, until the entire island is mapped. DFS would instead dive deep into one path before backtracking—different strategies, same island discovered.

Key Takeaway: BFS finds connected components just as effectively as DFS, exploring layer-by-layer and naturally providing distance information as a bonus.