How to Count Islands in a Grid with DFS and BFS

Counting islands in a grid is a great exercise for learning graph traversal.

In this problem, each cell can be:

• 1 → land
• 0 → water

An island is a group of land cells connected only by up, down, left, and right. Diagonal connections do not count.

The main idea

The solution is to walk through the entire grid and, whenever we find an unvisited land cell, explore the whole island.

The process looks like this:

1. scan every position in the grid
2. find a cell with value 1
3. count one new island
4. explore all connected neighbors with DFS or BFS
5. mark those cells as visited

The most important step is marking visited cells. In the session code, that was done by changing 1 to 0.

That works because a cell should not be counted again after it has already been processed.

Why change 1 to 0?

This is a simple way to remember that a cell was already handled.

If the cell stays as 1, the search may:

• revisit the same place
• count the same island more than once
• do unnecessary work

By changing it to 0, the cell behaves like water for the rest of the algorithm.

DFS: depth-first search

DFS explores one path as far as possible before coming back.

On a grid, that means:

• visit the current cell
• move to one neighbor
• keep moving through that neighbor’s neighbors
• repeat until no connected land remains

A simplified example:

function dfs(row, column) {
  if (row < 0 || row >= rows || column < 0 || column >= cols || grid[row][column] !== 1) return;
  grid[row][column] = 0;
  dfs(row + 1, column);
  dfs(row - 1, column);
  dfs(row, column + 1);
  dfs(row, column - 1);
}

When should you use DFS?

DFS is a good choice when you want a direct and compact solution.

Its downside is recursion: on very large inputs, that can be risky in some languages or environments.

BFS: breadth-first search

BFS explores the grid level by level.

It uses a queue:

1. put the starting cell in the queue
2. remove one cell from the queue
3. add all valid neighbors
4. repeat until the queue is empty

A simplified example:

function bfs(startR, startC) {
  const queue = [[startR, startC]];
  grid[startR][startC] = 0;
  for (let i = 0; i < queue.length; i++) {
    const [r, c] = queue[i];
    const neighbors = [
      [r + 1, c],
      [r - 1, c],
      [r, c + 1],
      [r, c - 1],
    ];
    for (const [nr, nc] of neighbors) {
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] !== 1) {
        continue;
      }
      grid[nr][nc] = 0;
      queue.push([nr, nc]);
    }
  }
}

When should you use BFS?

BFS is useful when you want to avoid recursion and prefer an iterative approach with a queue.

For this problem, it is an excellent alternative to DFS.

Do DFS and BFS solve the same problem?

Yes.

Both methods explore the same connected region of the grid. The difference is only the order of traversal:

• DFS goes deep first
• BFS goes layer by layer

Since the goal is only to count islands, both produce the same answer.

The solution structure

The outer logic is the same for DFS and BFS:

for (let row = 0; row < rows; r++) {
  for (let column = 0; column < cols; column++) {
    if (grid[row][column] === 1) {
      count++; // call BFS or DFS
    }
  }
}

This loop scans the entire grid. Whenever it finds a new land cell, it:

• increments the island counter
• calls a search to mark the whole island

Testing both versions with Bun

In the session, the tests were written with **bun test**, **test**, and **expect**.

The goal was to validate:

• empty or simple cases
• separated islands
• diagonals that do not count as connections
• larger grids with multiple islands
• invalid inputs
• the same input for both BFS and DFS

Example test:

test(name, () => {
  const bfsResult = countIslands(cloneGrid(grid));
  const dfsResult = countIslandsDFS(cloneGrid(grid));
  expect(bfsResult).toBe(expected);
  expect(dfsResult).toBe(expected);
  expect(bfsResult).toBe(dfsResult);
});

We use **cloneGrid** because both functions mutate the grid while marking visited cells.

What this exercise teaches

This problem is small, but it teaches several important ideas:

• scanning a grid
• recognizing connected components
• choosing between DFS and BFS
• marking visited states
• writing tests that compare two implementations

It is a very common problem in interviews and algorithm practice.

Conclusion

If you need to count islands in a grid, DFS and BFS are both correct and efficient solutions.

The choice between them depends more on style and environment constraints than on the final result.

• use DFS if you want a short recursive solution
• use BFS if you want an iterative queue-based version

The key is to remember to mark already visited cells so the same island is not counted twice.