Number of Islands BFS and DFS in DSA C - Deep Dive

Overview - Number of Islands BFS and DFS

What is it?

Number of Islands is a problem where you count how many separate groups of connected 'land' cells exist in a grid. Each cell can be water or land, and connected means horizontally or vertically adjacent. BFS (Breadth-First Search) and DFS (Depth-First Search) are two ways to explore these groups to count them.

Why it matters

This problem helps understand how to explore connected parts in a grid, which is common in maps, games, and image processing. Without this, we couldn't easily find separate regions or clusters in data, making many applications inefficient or impossible.

Where it fits

You should know basic arrays and loops before this. After this, you can learn graph traversal algorithms, advanced grid problems, and connected components in graphs.

Mental Model

Core Idea

Explore each land cell and mark all connected land cells as visited to count distinct islands.

Think of it like...

Imagine a map with patches of forest separated by rivers. To count forests, you walk through one patch fully before moving to the next, so you don't count the same forest twice.

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

Islands found:
  Island 1: top-left block of 1s
  Island 2: middle 1
  Island 3: bottom-right block of 1s

Build-Up - 6 Steps

1

Foundation

Understanding the Grid and Islands

Concept: Introduce the grid structure and what counts as an island.

A grid is a 2D array of 0s and 1s. 1 means land, 0 means water. Islands are groups of 1s connected horizontally or vertically. Diagonal connections do not count.

Result

You can identify which cells belong to land and which to water.

Knowing how the grid represents land and water is essential before exploring connected parts.

2

Foundation

Basic Traversal with DFS

Concept: Use Depth-First Search to explore connected land cells.

Start from a land cell, mark it visited, then recursively visit all adjacent land cells (up, down, left, right). This explores one island fully.

Result

You can visit all cells of one island starting from any land cell in it.

DFS helps explore all connected parts deeply before moving on, which is perfect for island counting.

3

Intermediate

Counting Islands Using DFS

🤔Before reading on: Do you think counting islands means visiting every cell once or multiple times? Commit to your answer.

Concept: Combine DFS with a loop over the grid to count islands.

Loop over each cell. If it's land and not visited, run DFS to mark the whole island visited and increase the island count by one.

Result

You get the total number of islands in the grid after checking all cells.

Understanding that each DFS call corresponds to one island prevents double counting.

4

Intermediate

Breadth-First Search (BFS) for Islands

🤔Before reading on: Will BFS visit cells in a different order than DFS? Commit to your answer.

Concept: Use BFS to explore islands level by level instead of deep first.

Start from a land cell, use a queue to visit neighbors in order. Mark visited cells to avoid repeats. BFS also fully explores one island before moving on.

Result

BFS also counts islands correctly, just explores cells in a different order.

Knowing BFS explores neighbors evenly helps understand alternative traversal strategies.

5

Advanced

Implementing BFS and DFS in C

🤔Before reading on: Do you think BFS or DFS is easier to implement in C? Commit to your answer.

Concept: Translate BFS and DFS logic into C code using arrays and queues or recursion.

Use a 2D array for the grid, a 2D boolean array for visited. For DFS, use recursion. For BFS, use a queue implemented with arrays or linked list. Mark visited cells to avoid revisiting.

Result

Complete C programs that output the number of islands for given grids.

Understanding how to implement these traversals in C solidifies the algorithm and memory management concepts.

6

Expert

Optimizations and Edge Cases

🤔Before reading on: Can you think of cases where BFS or DFS might be inefficient or cause errors? Commit to your answer.

Concept: Handle large grids, avoid stack overflow in DFS, and optimize memory usage.

For large grids, DFS recursion can cause stack overflow; BFS uses more memory but avoids this. Use iterative DFS with a stack to prevent overflow. Also, handle empty grids and all water or all land cases.

Result

Robust solutions that work efficiently on all inputs without crashing.

Knowing limitations and how to fix them prepares you for real-world coding challenges.

Under the Hood

Both DFS and BFS explore the grid by visiting connected land cells. DFS uses a call stack (or explicit stack) to go deep into one path before backtracking. BFS uses a queue to explore neighbors level by level. Visited cells are tracked to avoid infinite loops and double counting.

Why designed this way?

DFS and BFS come from graph theory to explore nodes and edges. Grids can be seen as graphs where each cell is a node connected to neighbors. These methods are simple, efficient, and guarantee visiting all connected nodes.

Grid cell connections:
┌───┬───┬───┐
│   │   │   │
├───┼───┼───┤
│   │ X │   │
├───┼───┼───┤
│   │   │   │
└───┴───┴───┘

X connects to up, down, left, right neighbors if they are land.

Myth Busters - 3 Common Misconceptions

Quick: Does diagonal adjacency count as connected land? Commit to yes or no.

Common Belief: Diagonal cells touching count as connected land for islands.

Reality: Only horizontal and vertical neighbors count as connected; diagonals do not.

Why it matters: Counting diagonals would merge separate islands incorrectly, giving wrong island counts.

Quick: Is BFS always faster than DFS for this problem? Commit to yes or no.

Common Belief: BFS is always faster than DFS for counting islands.

Reality: Both have similar time complexity; speed depends on implementation and input size.

Why it matters: Choosing BFS just for speed can waste memory or cause complexity without real benefit.

Quick: Can you count islands without marking visited cells? Commit to yes or no.

Common Belief: You can count islands by just checking cells without marking visited.

Reality: Without marking visited, you will count the same island multiple times.

Why it matters: Not marking visited leads to overcounting and incorrect results.

Expert Zone

1

Iterative DFS using a stack avoids recursion limits and is preferred in production for large grids.

2

Modifying the input grid to mark visited cells saves memory but destroys original data, which may be unacceptable.

3

BFS can be optimized with early stopping if only counting islands without needing full traversal.

When NOT to use

For extremely large grids or streaming data, union-find (disjoint set) data structures can be more efficient. Also, if diagonal connections count, BFS/DFS logic must be adjusted or replaced.

Production Patterns

In real systems, grids may be sparse; using adjacency lists or compressed representations improves performance. Also, parallel BFS/DFS can speed up counting on large maps.

Connections

Graph Connected Components

Number of Islands is a special case of finding connected components in a graph.

Understanding islands as connected components helps apply graph algorithms broadly.

Image Segmentation in Computer Vision

Both involve grouping connected pixels or regions based on similarity.

Knowing island counting aids in understanding how images are divided into meaningful parts.

Epidemiology Spread Models

Exploring connected regions is similar to tracing infection spread through contact networks.

Techniques for island counting help model and analyze disease spread patterns.

Common Pitfalls

#1 Not marking visited cells causes repeated counting of the same island.

Wrong approach:

void dfs(int r, int c) {
if (grid[r][c] == 1) {
dfs(r+1, c);
dfs(r-1, c);
dfs(r, c+1);
dfs(r, c-1);
}
}

// No visited array or marking

Correct approach:

void dfs(int r, int c) {
if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == 0 || visited[r][c]) return;
visited[r][c] = true;
dfs(r+1, c);
dfs(r-1, c);
dfs(r, c+1);
dfs(r, c-1);
}

Root cause:

Without visited tracking, recursion loops infinitely or counts islands multiple times.

#2 Counting diagonal neighbors as connected land.

Wrong approach:

Check neighbors including diagonals:
for (int dr = -1; dr <= 1; dr++) {
for (int dc = -1; dc <= 1; dc++) {
if (dr != 0 || dc != 0) dfs(r+dr, c+dc);
}
}

Correct approach:

Check only up, down, left, right neighbors:
int directions[4][2] = {{-1,0},{1,0},{0,-1},{0,1}};
for (int i=0; i<4; i++) {
dfs(r+directions[i][0], c+directions[i][1]);
}

Root cause:

Misunderstanding adjacency rules leads to merging separate islands.

#3 Using recursion for DFS on very large grids causing stack overflow.

Wrong approach:

Recursive DFS without limits on large input causes crash.

Correct approach:

Use iterative DFS with explicit stack:
stack.push(start);
while (!stack.empty()) {
cell = stack.pop();
// process and push neighbors
}

Root cause:

Recursion depth exceeds system limits on large inputs.

Key Takeaways

Number of Islands problem counts connected groups of land cells in a grid using graph traversal.

DFS and BFS are two main ways to explore and mark visited cells to avoid double counting.

Only horizontal and vertical neighbors count as connected, not diagonals.

Marking visited cells is essential to prevent infinite loops and overcounting.

Implementations must handle large inputs carefully to avoid stack overflow or memory issues.