Graph BFS - Connected Components / Island Counting — Graph Traversal Patterns (DFS & BFS)

Imagine you’re in a city after a heavy snowstorm. Some roads are blocked, and you want to find out which neighborhoods are still connected by open roads. You could start at one house, walk to all reachable houses, and mark them as “visited.” Then, you pick another unvisited house and repeat. Each time, you discover a new “connected component”—a cluster of places you can reach without crossing blocked roads.

This is the essence of the Connected Components / Island Counting subpattern using Breadth-First Search (BFS) in graphs. In programming, we often represent cities, islands, or even word transformations as graphs. BFS helps us systematically explore all nodes (or cells, or words) connected together, one layer at a time—like ripples spreading out from a stone dropped in a pond.

This pattern is super useful when you need to:

• Count how many separate groups exist (e.g., islands in a grid, clusters of friends in a network).
• Find the shortest path from one point to another (e.g., the quickest way out of a maze).
• Spread something step by step (e.g., how a rumor, fire, or infection propagates).

Everyday analogy: Think of BFS as organizing a neighborhood block party. You start with one house, invite all its immediate neighbors, then ask those neighbors to invite their neighbors, and so on—ensuring no one is missed and everyone is reached in the shortest number of steps.

Core Concepts

Let’s break down the key ideas behind this subpattern:

Breadth-First Search (BFS)

• BFS explores a graph level by level. Imagine standing at the center of a field and moving outward in rings—first visiting all spots 1 step away, then 2 steps, and so on.
• BFS uses a queue to remember which nodes to visit next, ensuring we process everything at the current “distance” before moving further out.

Connected Components / Island Counting

• A connected component is a group of nodes where each node can reach every other node in the group, but not nodes outside the group.
• In grids (like matrices), “islands” are clusters of adjacent cells (often 1s) surrounded by water (0s).

Key Data Structures

• Queue: For BFS, to process nodes in the correct order.
• Visited Set/Matrix: To avoid revisiting nodes or cells.
• Hash Table: Sometimes used to quickly check if a node/word has been seen (especially in word transformation problems).

Time & Space Complexity

• Time: BFS visits every node and edge once. For a grid, that’s O(m × n) where m and n are the grid’s dimensions.
  • Think of reading a book page by page, never skipping or rereading.
• Space: BFS needs space for the queue and the visited set/matrix. In the worst case, the queue can hold up to O(m × n) elements.

Mathematical Foundations

• BFS guarantees the shortest path in unweighted graphs because it explores all nodes at distance k before moving to distance k+1.
• For counting islands or components, BFS ensures every node in a component is discovered before moving to the next.

Implementation Approach

Let’s build a mental model for tackling these problems:

Step-by-Step Thinking

1. Visualize the Problem as a Graph

   • Is it a grid (matrix)? Each cell is a node; adjacent cells are connected.
   • Is it a set of words? Each word is a node; words differing by one letter are connected.

2. Identify What Needs to Be Explored

   • Are you counting groups (islands/components)?
   • Are you finding the shortest path or minimum steps?

3. Set Up Visited Tracking

   • For grids: Use a boolean matrix or mark cells as visited.
   • For words: Use a hash set to track visited words.

4. Use a Queue for BFS

   • Start from each unvisited node/cell/word.
   • Add it to the queue and mark as visited.
   • While the queue isn’t empty:
     • Dequeue the current node.
     • For each neighbor (adjacent cell/word):
       • If not visited, add to the queue and mark as visited.

5. Handle Edge Cases

   • Empty grids or lists: Return 0 or -1 as appropriate.
   • Blocked start/end points: Check before starting BFS.
   • Multiple starting points: Sometimes, you need to enqueue all sources at once (e.g., all rotten oranges).

Decision Tree

• Counting Groups? → BFS from every unvisited node, incrementing a counter.
• Shortest Path? → BFS from the start node, tracking steps.
• Multiple Sources? → Enqueue all sources at the start.

Common Pitfalls

• Forgetting to mark nodes as visited (can cause infinite loops).
• Not checking boundaries in grids (can access invalid cells).
• Not handling diagonal moves when required.

Example: BFS in a Grid (e.g., “Rotting Oranges”)

• For each rotten orange, enqueue its position.
• For each minute, process all oranges in the queue (current layer).
• For each, rot adjacent fresh oranges and enqueue them for the next minute.

C++ Code Example

Let’s walk through a BFS implementation for the “Rotting Oranges” problem.

1#include <vector>
2#include <queue>
3using namespace std;
4
5// Function to compute the minimum minutes to rot all oranges
6int orangesRotting(vector<vector<int>>& grid) {
7    int rows = grid.size();
8    int cols = grid[0].size();
9    queue<pair<int, int>> q; // Queue for BFS: stores positions of rotten oranges
10    int freshCount = 0;      // Count of fresh oranges
11
12    // Step 1: Initialize the queue with all initially rotten oranges
13    for (int r = 0; r < rows; ++r) {
14        for (int c = 0; c < cols; ++c) {
15            if (grid[r][c] == 2) {
16                q.push({r, c}); // Rotten orange found
17            } else if (grid[r][c] == 1) {
18                ++freshCount;   // Count fresh oranges
19            }
20        }
21    }
22
23    // Directions for 4-adjacent cells (up, down, left, right)
24    vector<pair<int, int>> directions = {{-1,0},{1,0},{0,-1},{0,1}};
25    int minutes = 0;
26
27    // Step 2: BFS to rot adjacent fresh oranges minute by minute
28    while (!q.empty() && freshCount > 0) {
29        int size = q.size(); // Number of oranges to process this minute
30        for (int i = 0; i < size; ++i) {
31            auto [r, c] = q.front(); q.pop();
32            // Check all 4 directions
33            for (auto [dr, dc] : directions) {
34                int nr = r + dr, nc = c + dc;
35                // If neighbor is in bounds and is a fresh orange
36                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] == 1) {
37                    grid[nr][nc] = 2; // Rot the orange
38                    --freshCount;     // One less fresh orange
39                    q.push({nr, nc}); // Add to queue for next minute
40                }
41            }
42        }
43        ++minutes; // One minute passed
44    }
45
46    // If there are fresh oranges left, return -1
47    return freshCount == 0 ? minutes : -1;
48}

Key Explanations:

• We enqueue all rotten oranges at the start, so BFS spreads rot in waves (minutes).
• Each loop iteration represents one minute.
• We track the number of fresh oranges; if any remain at the end, return -1.
• The queue ensures we process oranges in the correct order (all at distance k before k+1).

Problem Analysis: “Rotting Oranges”

Let’s think about “Rotting Oranges” step by step:

1. Intuition:
   Imagine a room full of oranges. Some are rotten, some are fresh. Every minute, rot spreads to adjacent fresh oranges. We want to know the minimum time until all oranges are rotten—or if it’s impossible.

2. Graph Model:

   • The grid is a graph: each cell is a node.
   • Edges connect 4-directionally adjacent cells.
   • Rotten oranges are “sources” from which rot spreads.

3. BFS Approach:

   • Start by enqueuing all rotten oranges. This is like starting BFS from multiple sources.
   • Each minute, process all oranges that are currently rotten (all nodes at the current BFS level).
   • For each, rot any adjacent fresh oranges and enqueue them for the next minute.
   • Track the number of fresh oranges. If any remain after BFS, return -1.

4. Why BFS?

   • BFS naturally models the “spread” over time, ensuring we count minutes correctly.
   • Each level of BFS corresponds to one minute passing.

5. Edge Cases:

   • If there are no fresh oranges at the start, return 0.
   • If some fresh oranges are completely isolated (surrounded by empty cells), they’ll never rot—so return -1.

6. Connecting Back:

   • This is a classic “connected components” problem where we’re interested in how a process spreads through a component.
   • BFS is ideal for simulating step-by-step spread and finding the minimum time.

By following this approach, you can confidently tackle similar problems involving spreading, shortest paths, or counting clusters in grids.

Practice Tips

• Signals to Recognize This Pattern:

  • Grids or graphs where you need to count groups or simulate spreading.
  • Questions about “minimum steps,” “shortest path,” or “how many clusters.”
  • Multiple starting points or sources.

• Aha! Moments:

  • Realizing that BFS from all sources at once models simultaneous spread.
  • Understanding that BFS guarantees the shortest path in unweighted graphs.

• Debugging Tips:

  • Always mark nodes/cells as visited as soon as you enqueue them.
  • Double-check boundary conditions in grids.
  • Use print statements to visualize queue contents and visited status.

• Memory Tricks:

  • “BFS = Breadth-First = By Floor Steps” (imagine exploring a building floor by floor).
  • For grids, think of coloring each group as you discover it.

With practice, you’ll spot these patterns quickly and apply BFS with confidence!