Number of Islands BFS and DFS in DSA C++ - Build from Scratch

Number of Islands BFS and DFS

📖 Scenario: Imagine you have a map represented as a grid of water and land cells. You want to find out how many separate islands are on the map. An island is a group of connected land cells (horizontally or vertically). This is useful in real-world tasks like counting forest patches or lakes on satellite images.

🎯 Goal: You will build a program that counts the number of islands in a grid using two common methods: Breadth-First Search (BFS) and Depth-First Search (DFS). You will first set up the grid, then add helper variables, implement BFS and DFS to explore islands, and finally print the count of islands found.

📋 What You'll Learn

Create a 2D vector called grid with exact values representing land ('1') and water ('0')

Create integer variables rows and cols to store grid dimensions

Implement a BFS function called bfs that marks connected land cells as visited

Implement a DFS function called dfs that marks connected land cells as visited

Count islands by scanning the grid and using BFS or DFS to explore each island

Print the number of islands found using BFS and DFS

💡 Why This Matters

🌍 Real World

Counting islands or connected regions is useful in satellite image analysis, game maps, and network connectivity.

💼 Career

Understanding BFS and DFS for grid problems is a common interview topic and helps in solving real-world graph and matrix problems.

1

Set up the grid

Create a 2D vector of characters called grid with these exact rows: {'1','1','0','0','0'}, {'1','1','0','0','0'}, {'0','0','1','0','0'}, {'0','0','0','1','1'}.

DSA C++

# Create the 2D vector grid with the exact values
# Your code here

Hint

Use vector> grid = { ... }; with the exact rows given.

2

Add grid dimensions

Create two integer variables called rows and cols that store the number of rows and columns in grid respectively.

DSA C++

#include 
#include 
using namespace std;

vector> grid = {
    {'1','1','0','0','0'},
    {'1','1','0','0','0'},
    {'0','0','1','0','0'},
    {'0','0','0','1','1'}
};

// Create rows and cols variables
# Your code here

Hint

Use int rows = grid.size(); and int cols = grid[0].size(); to get dimensions.

3

Implement BFS and DFS functions

Implement two functions: void bfs(int r, int c, vector>& grid, vector>& visited) and void dfs(int r, int c, vector>& grid, vector>& visited). Both should mark all connected land cells starting from (r, c) as visited. Use a queue for BFS and recursion for DFS.

DSA C++

void bfs(int r, int c, vector>& grid, vector>& visited) {
    queue> q;
    q.push({r, c});
    visited[r][c] = true;
    int dr[] = {-1, 1, 0, 0};
    int dc[] = {0, 0, -1, 1};
    while (!q.empty()) {
        auto [row, col] = q.front();
        q.pop();
        for (int i = 0; i = 0 && nr = 0 && nc >& grid, vector>& visited) {
    if (r = rows || c = cols || grid[r][c] == '0' || visited[r][c])
        return;
    visited[r][c] = true;
    dfs(r - 1, c, grid, visited);
    dfs(r + 1, c, grid, visited);
    dfs(r, c - 1, grid, visited);
    dfs(r, c + 1, grid, visited);
}
// Count islands using BFS and DFS

Hint

Use a queue and loop for BFS. Use recursion for DFS. Mark visited cells to avoid repeats.

4

Count islands and print results

Create two 2D boolean vectors called visitedBFS and visitedDFS initialized to false. Use loops to scan grid. For each unvisited land cell, call bfs or dfs to mark the island. Count how many times you call these functions. Finally, print the counts with cout in this exact format: "Number of islands (BFS): X" and "Number of islands (DFS): Y" where X and Y are the counts.

DSA C++

Hint

Use two visited arrays and count islands by calling bfs or dfs on unvisited land cells. Print counts exactly as shown.

Practice

1. What does the "Number of Islands" problem ask you to find in a 2D grid of '1's (land) and '0's (water)?

easy

A. Count total number of '1's in the grid

B. Count how many separate groups of connected '1's exist

C. Find the largest island size

D. Find the shortest path between two islands

Solution

1. Step 1: Understand the problem definition

   The problem asks to count distinct islands, where an island is a group of connected '1's horizontally or vertically.

2. Step 2: Clarify what is being counted

   We count how many separate clusters of '1's exist, not the total number of '1's or sizes.

3. Final Answer:

   Count how many separate groups of connected '1's exist -> Option B

4. Quick Check:

   Number of islands = count of connected '1' groups [OK]

Hint: Islands = groups of connected '1's, count groups not cells [OK]

Common Mistakes:

• Counting total '1's instead of groups
• Including diagonal connections as connected
• Confusing island size with island count

2. Which of the following C++ code snippets correctly initializes a 2D vector grid of chars with given rows and columns filled with '0'?

easy

A. std::vector grid(rows, std::vector<char>(cols, '0'));

B. std::vector<char> grid(rows, std::vector<char>(cols, '0'));

C. std::vector grid(cols, std::vector<char>(rows, '0'));

D. std::vector grid(rows, cols, '0');

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector of chars, use vector of vectors: outer vector size = rows, inner vector size = cols.

2. Step 2: Check each option

   std::vector grid(rows, std::vector<char>(cols, '0')); correctly creates 'rows' vectors each with 'cols' chars initialized to '0'. Others have wrong types or parameters.

3. Final Answer:

   std::vector grid(rows, std::vector<char>(cols, '0')); -> Option A

4. Quick Check:

   2D vector init = vector of vectors with sizes [OK]

Hint: Use vector(rows, vector<char>(cols, '0')) [OK]

Common Mistakes:

• Swapping rows and cols sizes
• Using wrong vector types
• Trying to initialize 2D vector with three parameters

3. Given the following grid and BFS-based code snippet to count islands, what is the output?

std::vector grid = {
  {'1','1','0','0'},
  {'1','0','0','1'},
  {'0','0','1','1'},
  {'0','0','0','0'}
};
int countIslands(const std::vector& grid) {
  int count = 0;
  int rows = grid.size();
  int cols = grid[0].size();
  std::vector visited(rows, std::vector<bool>(cols, false));
  std::queue> q;
  int directions[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
  for(int i=0; i=0 && nr=0 && nc

medium

A. 3

B. 4

C. 2

D. 1

Solution

1. Step 1: Identify islands in the grid

   Islands are groups of connected '1's. Here, islands are: top-left cluster (3 cells), single '1' at (1,3), and bottom cluster (2 cells at (2,2),(2,3)). Total 3 islands.

2. Step 2: Understand BFS traversal

   The BFS marks all connected '1's visited per island, so count increments once per island found.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count islands = 3 [OK]

Hint: Count connected groups by BFS marking visited [OK]

Common Mistakes:

• Counting diagonal connections as islands
• Missing isolated '1's as separate islands
• Not marking visited correctly causing overcount

4. The following DFS code for counting islands has a bug. What is the bug?

void dfs(int r, int c, std::vector& grid) {
  int rows = grid.size();
  int cols = grid[0].size();
  if(r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0')
    return;
  grid[r][c] = '0';
  dfs(r+1, c, grid);
  dfs(r-1, c, grid);
  dfs(r, c+1, grid);
  dfs(r, c-1, grid);
}

int numIslands(std::vector& grid) {
  int count = 0;
  for(int i=0; i

medium

A. The base case does not check for visited cells

B. The DFS does not check boundaries correctly

C. The DFS does not mark visited cells, causing infinite recursion

D. The grid is modified during DFS, which is incorrect

Solution

1. Step 1: Analyze DFS grid modification

   The DFS marks visited cells by changing '1' to '0' in the original grid, modifying input.

2. Step 2: Identify why this is a bug

   Modifying input grid may be unintended side effect; better to use a separate visited array to avoid altering input data.

3. Final Answer:

   The grid is modified during DFS, which is incorrect -> Option D

4. Quick Check:

   Modifying input grid = bug [OK]

Hint: Avoid changing input grid; use visited array instead [OK]

Common Mistakes:

• Ignoring that grid is changed in-place
• Assuming no visited tracking needed
• Misreading boundary checks as incorrect

5. You want to count islands in a grid where diagonal connections also count as connected (8 directions). How should you modify the BFS or DFS approach?

hard

A. Count islands by summing all '1's without traversal

B. Only check horizontal neighbors, ignore vertical and diagonal

C. Add diagonal directions (like (1,1), (1,-1), (-1,1), (-1,-1)) to the directions array

D. Use BFS for horizontal and DFS for vertical connections separately

Solution

1. Step 1: Understand connectivity change

   Diagonal connections mean neighbors include 8 directions: up, down, left, right, and 4 diagonals.

2. Step 2: Modify directions array

   Add diagonal moves (1,1), (1,-1), (-1,1), (-1,-1) to directions used in BFS or DFS to explore all connected neighbors.

3. Final Answer:

   Add diagonal directions (like (1,1), (1,-1), (-1,1), (-1,-1)) to the directions array -> Option C

4. Quick Check:

   Include all 8 neighbors for diagonal connectivity [OK]

Hint: Add diagonal moves to directions for 8-way connectivity [OK]

Common Mistakes:

• Ignoring diagonal neighbors
• Counting only horizontal or vertical neighbors
• Trying to count without traversal