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

Counting Connected Components

Iterate through all vertices, running DFS or BFS on unvisited vertices to count total number of components.

Counting Connected Components

You'll learn: How to count the total number of separate "islands" in a graph by systematically visiting all vertices.

The Core Idea

Imagine a map with several isolated island groups. To count how many separate groups exist, you'd visit one island, explore its entire group, mark them all as visited, then look for the next unvisited island and repeat.

In graph terms, a connected component is a group of vertices that can reach each other through edges, but cannot reach vertices in other components. To count them, we iterate through all vertices in the graph. Each time we encounter an unvisited vertex, we've discovered a new component—we increment our counter and run a full DFS or BFS from that vertex to mark everything in its component as visited.

The Algorithm

  1. Initialize a visited array to track which vertices you've seen
  2. Set componentCount = 0
  3. For each vertex v in the graph:
    • If v is not visited:
      • Increment componentCount (found a new component!)
      • Run DFS or BFS starting from v to mark all reachable vertices as visited
  4. Return componentCount

The beauty is that DFS/BFS naturally explores one entire component before returning, so each traversal "consumes" exactly one component.

Why It Works

Every time you find an unvisited vertex, it must belong to a component you haven't explored yet (otherwise it would already be marked visited from a previous traversal). The subsequent DFS/BFS marks all vertices in that component, ensuring you never double-count.

Key Takeaway: Counting connected components requires iterating through all vertices and launching a DFS or BFS from each unvisited one—the number of launches equals the number of components.