Number of Islands BFS and DFS in DSA C

Mental Model

We find groups of connected land cells by exploring neighbors until no new land is found, counting each group as one island.

Analogy: Imagine walking through a forest and marking all connected trees as one cluster before moving to the next cluster.

Grid example:
1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

1 = land, 0 = water

Dry Run Walkthrough

Input: grid: [[1,1,0,0,0],[1,1,0,0,0],[0,0,1,0,0],[0,0,0,1,1]]

Goal: Count how many separate islands (connected groups of 1s) are in the grid

Step 1: Start at (0,0), find land, begin BFS/DFS to mark connected land

Visited (0,0), (0,1), (1,0), (1,1) marked as visited
Grid:
X X 0 0 0
X X 0 0 0
0 0 1 0 0
0 0 0 1 1

Why: We mark all connected land in this cluster to count one island

Step 2: Move to (0,2), water, skip

No change
Grid:
X X 0 0 0
X X 0 0 0
0 0 1 0 0
0 0 0 1 1

Why: Water cells do not belong to islands

Step 3: At (2,2), find new land, start BFS/DFS to mark connected land

Visited (2,2)
Grid:
X X 0 0 0
X X 0 0 0
0 0 X 0 0
0 0 0 1 1

Why: New island found, mark connected land

Step 4: At (3,3), find new land, start BFS/DFS to mark connected land

Visited (3,3), (3,4)
Grid:
X X 0 0 0
X X 0 0 0
0 0 X 0 0
0 0 0 X X

Why: Third island found, mark connected land

Result:

Final visited grid:
X X 0 0 0
X X 0 0 0
0 0 X 0 0
0 0 0 X X
Number of islands = 3

Annotated Code

DSA C

#include <stdio.h>
#include <stdbool.h>

#define ROWS 4
#define COLS 5

// Directions for neighbors (up, down, left, right)
int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};

void dfs(int grid[ROWS][COLS], bool visited[ROWS][COLS], int r, int c) {
    if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return; // boundary check
    if (visited[r][c]) return; // already visited
    if (grid[r][c] == 0) return; // water cell

    visited[r][c] = true; // mark current land as visited

    for (int i = 0; i < 4; i++) {
        int nr = r + directions[i][0];
        int nc = c + directions[i][1];
        dfs(grid, visited, nr, nc); // explore neighbors
    }
}

int numIslands(int grid[ROWS][COLS]) {
    bool visited[ROWS][COLS] = {{false}};
    int count = 0;

    for (int r = 0; r < ROWS; r++) {
        for (int c = 0; c < COLS; c++) {
            if (grid[r][c] == 1 && !visited[r][c]) {
                dfs(grid, visited, r, c); // mark all connected land
                count++;
            }
        }
    }
    return count;
}

int main() {
    int grid[ROWS][COLS] = {
        {1,1,0,0,0},
        {1,1,0,0,0},
        {0,0,1,0,0},
        {0,0,0,1,1}
    };

    int islands = numIslands(grid);
    printf("Number of islands = %d\n", islands);
    return 0;
}

if (r < 0 || r >= ROWS || c < 0 || c >= COLS) return;

stop if out of grid bounds

if (visited[r][c]) return;

skip if cell already visited

if (grid[r][c] == 0) return;

skip water cells

visited[r][c] = true;

mark current land cell visited

for (int i = 0; i < 4; i++) { dfs(grid, visited, r + directions[i][0], c + directions[i][1]); }

explore all four neighbors recursively

if (grid[r][c] == 1 && !visited[r][c]) { dfs(grid, visited, r, c); count++; }

start DFS for new island and increment count

Output

Number of islands = 3

Complexity Analysis

Time: O(R*C) because each cell is visited once during DFS

Space: O(R*C) for the visited array and recursion stack in worst case

vs Alternative: Compared to BFS, DFS uses recursion stack; both have similar time but BFS uses queue for iteration

Edge Cases

Empty grid (all water)

Returns 0 islands as no land is found

DSA C

if (grid[r][c] == 1 && !visited[r][c]) {

Grid with one big island (all land)

Returns 1 island after marking all cells visited

DSA C

visited[r][c] = true;

Grid with multiple small islands separated by water

Counts each separate cluster correctly

DSA C

dfs(grid, visited, r, c);

When to Use This Pattern

When you see a grid and need to count connected groups, use DFS or BFS to explore neighbors and mark visited cells to avoid double counting.

Common Mistakes

Mistake: Not marking visited cells, causing infinite loops or overcounting
Fix: Always mark cells as visited before exploring neighbors

Mistake: Checking neighbors outside grid boundaries
Fix: Add boundary checks before accessing neighbors

Summary

Counts how many connected groups of land cells (islands) are in a grid using DFS or BFS.

Use when you need to find clusters or connected components in a 2D grid.

The key is to explore all connected neighbors from each unvisited land cell to mark one whole island.