Graph DSA: Number of Islands & Number of Connected Components in Matrix

This chapter explores how to apply graph traversal algorithms (BFS and DFS) to non-traditional graph structures—specifically 2D grids and matrices. We will solve the classic "Number of Islands" problem, learning how to map matrix cells to graph nodes, leverage 8-way directional connectivity, and implement clean traversal workflows.

1. Problem Statement & Definition

You are given a 2D grid of size $N \times M$ , where:

0 represents water.
1 represents land.

An island is formed by connecting adjacent lands horizontally, vertically, or diagonally in all 8 directions. Your task is to find and return the total number of islands present in the grid.

Real-Life Analogy: Aerial Survey of Archipelagos

Mental Hook: Imagine flying over an ocean in a helicopter. The ocean is filled with scattered patches of land. If you land on a piece of land and walk across every connected landmass (using north, south, east, west, and diagonal paths), you will eventually cover that entire island without getting your feet wet. Once you finish exploring that island, you take off, fly over the open water (0), land on a new unvisited patch of land (1), and count it as your second island. The number of times you must take off and land on a new unvisited island equals the total number of islands.

2. Why Is This a Graph Problem?

At first glance, a 2D matrix looks like a standard table or grid. However, we can reframe it through a graph lens:

Nodes/Vertices: Every individual cell in the matrix represents a node.
Edges: A node is connected to its neighbors if they contain 1 (land) and are adjacent in any of the 8 possible directions.

Structure & Concept Flow

Grid Cells:

[0][0] = 0 | [0][1] = 1 (Node A)

----------------------------------

[1][0] = 0 | [1][1] = 1 (Node B)

If we start a traversal (BFS or DFS) from any node containing 1, the traversal will ripple outward, visiting all connected land cells until it hits water (0) or the grid boundary.

3. Core Mental Model: The Traversal Approach

To count the total number of islands, we can iterate through every cell in the matrix. Whenever we encounter a 1 that has not yet been visited, it means we have discovered a brand-new island.

We increment our island_count by 1.
We trigger a BFS (or DFS) traversal from this cell.
The traversal marks all reachable connected lands as visited.
We continue scanning the matrix. Any future 1 that is already marked as visited belongs to an island we already counted.

Structure & Concept Flow

Matrix Scan

Encounter unvisited '1'

+--> Increment island_count++

+--> Launch BFS/DFS traversal

Marks all 8-directionally connected '1's as visited

Resume Matrix Scan

4. Handling 8-Way Neighbors Using Delta Loops

In traditional graphs, neighbors are fetched via an adjacency list. In a 2D matrix, neighbors are spatial coordinates. Standing at cell (row, col), its 8 neighbors lie in surrounding rows and columns:

\text{Neighbor Row} = \text{row} + \Delta r

\text{Neighbor Col} = \text{col} + \Delta c

Where both $\Delta r$ and $\Delta c$ range independently from -1 to +1.

Delta Offset Matrix Explanation

Instead of writing 8 repetitive if statements, we use nested loops for $\Delta r$ and $\Delta c$ :

C++

for (int delta_row = -1; delta_row <= 1; delta_row++) {
    for (int delta_col = -1; delta_col <= 1; delta_col++) {
        int neighbor_row = row + delta_row;
        int neighbor_col = col + delta_col;
        // Validate and process neighbor...
    }
}

Note: When $\Delta r = 0$ and $\Delta c = 0$ , the loop points to the current cell itself. Our algorithm naturally skips this because the current cell is already marked as visited.

5. Breadth-First Search (BFS) Implementation

Below is the complete solution implemented in both Java and C++.

C++ Implementation

C++

#include <vector>
#include <queue>

using namespace std;

class Solution {
private:
    void bfs(int startRow, int startCol, vector<vector<int>>& visited, const vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        visited[startRow][startCol] = 1;
        queue<pair<int, int>> q;
        q.push({startRow, startCol});
        
        while (!q.empty()) {
            int row = q.front().first;
            int col = q.front().second;
            q.pop();
            
            // Traverse all 8 neighbors
            for (int deltaRow = -1; deltaRow <= 1; deltaRow++) {
                for (int deltaCol = -1; deltaCol <= 1; deltaCol++) {
                    int neighborRow = row + deltaRow;
                    int neighborCol = col + deltaCol;
                    
                    // Check boundary validity, whether it's land ('1'), and unvisited
                    if (neighborRow >= 0 && neighborRow < n && 
                        neighborCol >= 0 && neighborCol < m && 
                        grid[neighborRow][neighborCol] == '1' && 
                        !visited[neighborRow][neighborCol]) {
                        
                        visited[neighborRow][neighborCol] = 1;
                        q.push({neighborRow, neighborCol});
                    }
                }
            }
        }
    }

public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();
        
        // Create a 2D visited array initialized to 0
        vector<vector<int>> visited(n, vector<int>(m, 0));
        int islandCount = 0;
        
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < m; col++) {
                // If cell is land ('1') and not yet visited, it's a new island
                if (grid[row][col] == '1' && !visited[row][col]) {
                    islandCount++;
                    bfs(row, col, visited, grid);
                }
            }
        }
        
        return islandCount;
    }
};

6. Step-by-Step Execution Flow Walkthrough

Let's trace how the algorithm processes a small $3 \times 3$ grid:

CODE

Grid:
1 1 0
0 1 0
1 0 0

Scan starts at (0, 0): Value is '1', visited[0][0] is 0.
- Increment islandCount = 1.
- Call bfs(0, 0).
- visited[0][0] = 1, pushed to queue [(0,0)].
BFS Expansion from (0, 0):
- Pop (0, 0). Check 8 neighbors.
- Neighbor (0, 1) is '1' and unvisited -> Mark visited 1, push (0, 1).
- Neighbor (1, 1) is '1' and unvisited -> Mark visited 1, push (1, 1).
- Queue processes (0, 1) and (1, 1), marking their connected neighbors (e.g., (1, 1) reaches (0,0) which is visited, etc.).
Scan resumes:
- Iterates through (0, 1), (0, 2), (1, 0), (1, 1)—all are skipped because they are already marked as visited or are water (0).
Scan reaches (2, 0): Value is '1', visited[2][0] is 0.
- Increment islandCount = 2.
- Call bfs(2, 0). Mark visited and process.
Final Result: Scan completes. Total islands found = 2.

7. Complexity Analysis

Complexity Type	Analysis	Rationale
Time Complexity	$O(N \times M + N \times M \times 9)$ $\approx O(N \times M)$	We traverse every matrix cell once ( $N \times M$ ). For each cell, we check its 9 potential neighbor directions (including self, which is skipped). Thus, time scales linearly with total cells.
Space Complexity	$O(N \times M)$	We allocate a 2D `visited` matrix of size $N \times M$ . In the worst-case scenario where all cells form a single giant island, the BFS queue will also hold up to $N \times M$ coordinates.

Optimization Note: To achieve $O(1)$ auxiliary space, some implementations mutate the input grid directly—changing visited '1' characters to '0' or a special visited symbol. However, creating a separate visited array is cleaner and preserves read-only input contract requirements in production environments.

8. Summary and Key Takeaways

Matrix as a Graph: Any 2D grid can be modeled as a graph where cells are nodes and valid adjacent matching values form undirected edges.
Problem Mapping: The "Number of Islands" problem is identical to finding the Number of Connected Components in an undirected graph.
Starting Points: Unvisited land cells (1) act as starting triggers for our graph traversal (bfs or dfs). Every time a new traversal is initiated from an unvisited land cell, the island count increments by 1.
8-Way Connectivity: When diagonal moves are permitted, nested loops with delta offsets ( $\Delta r, \Delta c \in [-1, 1]$ ) provide a compact, bug-free way to explore all 8 surrounding neighbors.
Boundary & State Validation: Always validate matrix boundaries (0 <= row < n, 0 <= col < m) before checking cell values or visited states to prevent segmentation faults or index out-of-bounds exceptions.