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

Number of Islands BFS and DFS

📖 Scenario: You are working with a map represented as a grid of water and land cells. Each cell is either '1' (land) or '0' (water). Your task is to find how many separate islands are on the map. An island is a group of connected lands horizontally or vertically.

🎯 Goal: Build a program that counts the number of islands in the given grid using both Breadth-First Search (BFS) and Depth-First Search (DFS) methods.

📋 What You'll Learn

Create a 2D char array called grid with the exact values given.

Create an integer variable rows and cols to store grid dimensions.

Implement a BFS method called BFS to explore connected lands.

Implement a DFS method called DFS to explore connected lands.

Count islands using BFS and DFS separately and store results in islandCountBFS and islandCountDFS.

Print the counts exactly as specified.

💡 Why This Matters

🌍 Real World

Counting islands in a grid is similar to detecting connected regions in maps, satellite images, or game maps.

💼 Career

Understanding BFS and DFS for grid traversal is essential for roles in software development, game programming, and data analysis.

1

Create the grid data structure

Create a 2D char array called grid with these exact values: {'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 char array grid with the exact values
# Your code here

Hint

Use a jagged array of chars to represent the grid exactly as shown.

2

Set up grid dimensions

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

DSA C#

char[][] grid = new char[][]
{
    new char[] {'1','1','0','0','0'},
    new char[] {'1','1','0','0','0'},
    new char[] {'0','0','1','0','0'},
    new char[] {'0','0','0','1','1'}
};

// Create rows and cols variables
# Your code here

Hint

Use grid.Length for rows and grid[0].Length for cols.

3

Implement BFS and DFS methods

Implement two methods: BFS and DFS. Both take int r, int c, char[][] grid, bool[][] visited, int rows, and int cols as parameters. They mark all connected land cells starting from (r, c) as visited. Use a queue for BFS and recursion for DFS.

DSA C#

char[][] grid = new char[][]
{
    new char[] {'1','1','0','0','0'},
    new char[] {'1','1','0','0','0'},
    new char[] {'0','0','1','0','0'},
    new char[] {'0','0','0','1','1'}
};

int rows = grid.Length;
int cols = grid[0].Length;

// Implement BFS method
// Implement DFS method
# Your code here

Hint

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

4

Count islands and print results

Create two boolean 2D arrays called visitedBFS and visitedDFS with the same size as grid. Use nested loops to count islands by calling BFS and DFS respectively when you find unvisited land. Store counts in islandCountBFS and islandCountDFS. Finally, print the counts exactly as: "Number of islands (BFS): {islandCountBFS}" and "Number of islands (DFS): {islandCountDFS}".

DSA C#

Hint

Initialize visited arrays, loop through grid cells, call BFS or DFS when you find unvisited land, increment counts, and print results.

Practice

1. What does the "Number of Islands" problem typically ask you to find in a 2D grid?

easy

A. Calculate the perimeter of islands

B. Find the largest island size

C. Replace all '1's with '0's

D. Count how many groups of connected '1's (land) exist

Solution

1. Step 1: Understand the problem statement

   The problem asks to count distinct islands, where islands are groups of connected '1's (land) in the grid.

2. Step 2: Identify what is being counted

   We count how many separate groups of connected land cells exist, not their size or perimeter.

3. Final Answer:

   Count how many groups of connected '1's (land) exist -> Option D

4. Quick Check:

   Number of islands = count of connected land groups [OK]

Hint: Islands = connected groups of '1's in grid [OK]

Common Mistakes:

• Confusing island count with island size
• Counting water cells instead of land
• Ignoring connectivity rules (horizontal and vertical)

2. Which of the following C# code snippets correctly initializes a 2D char array representing a grid for the Number of Islands problem?

easy

A. char[,] grid = new char[][] { {'1','0'}, {'0','1'} };

B. char[,] grid = { {'1','0'}, {'0','1'} };

C. char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} };

D. char[][] grid = new char[2][2] { {'1','0'}, {'0','1'} };

Solution

1. Step 1: Understand C# 2D array initialization

   In C#, jagged arrays (array of arrays) are declared as char[][] and initialized with new char[][] and inner arrays. Number of Islands uses jagged arrays for grid[r][c] access and grid[0].Length.

2. Step 2: Check each option's syntax

   char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} };: char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} }; correctly uses jagged array syntax.
   char[,] grid = new char[][] { {'1','0'}, {'0','1'} };: declares char[,] (rectangular) but tries jagged init - type mismatch.
   char[,] grid = { {'1','0'}, {'0','1'} };: valid rectangular char[,], but incompatible with grid[r][c] and grid[0].Length.
   char[][] grid = new char[2][2] { {'1','0'}, {'0','1'} };: new char[2][2] invalid syntax (incorrect brackets).

3. Final Answer:

   char[][] grid = new char[][] { new char[] {'1','0'}, new char[] {'0','1'} }; -> Option C

4. Quick Check:

   Jagged array with new keyword = correct syntax [OK]

Hint: Use 'new' keyword for jagged arrays in C# [OK]

Common Mistakes:

• Omitting 'new' keyword in array initialization
• Confusing jagged arrays with rectangular arrays
• Using wrong braces or missing inner arrays

3. Given the following grid and BFS-based code snippet, what is the output (number of islands)?

char[][] grid = new char[][] {
  new char[] {'1','1','0','0'},
  new char[] {'1','0','0','1'},
  new char[] {'0','0','1','1'},
  new char[] {'0','0','0','0'}
};

int CountIslands(char[][] grid) {
  int count = 0;
  int rows = grid.Length;
  int cols = grid[0].Length;
  bool[][] visited = new bool[rows][];
  for (int i = 0; i < rows; i++) visited[i] = new bool[cols];

  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (grid[r][c] == '1' && !visited[r][c]) {
        BFS(r, c, grid, visited);
        count++;
      }
    }
  }
  return count;
}

void BFS(int r, int c, char[][] grid, bool[][] visited) {
  int[] dr = { -1, 1, 0, 0 };
  int[] dc = { 0, 0, -1, 1 };
  Queue<(int, int)> queue = new Queue<(int, int)>();
  queue.Enqueue((r, c));
  visited[r][c] = true;

  while (queue.Count > 0) {
    var (row, col) = queue.Dequeue();
    for (int i = 0; i < 4; i++) {
      int nr = row + dr[i];
      int nc = col + dc[i];
      if (nr >= 0 && nr < grid.Length && nc >= 0 && nc < grid[0].Length && grid[nr][nc] == '1' && !visited[nr][nc]) {
        queue.Enqueue((nr, nc));
        visited[nr][nc] = true;
      }
    }
  }
}

Console.WriteLine(CountIslands(grid));

medium

A. 3

B. 2

C. 4

D. 1

Solution

1. Step 1: Analyze the grid for connected islands

   Islands are groups of '1's connected horizontally or vertically. The grid has these islands:
   - Island 1: (0,0),(0,1),(1,0)
   - Island 2: (1,3)
   - Island 3: (2,2),(2,3)

2. Step 2: BFS visits each island once

   The BFS marks all connected '1's as visited. Each BFS call increments count by 1. Total BFS calls = number of islands = 3.

3. Final Answer:

   3 -> Option A

4. Quick Check:

   Count islands by BFS calls = 3 [OK]

Hint: Count BFS calls on unvisited '1's = number of islands [OK]

Common Mistakes:

• Counting diagonally connected '1's as one island
• Missing isolated single '1's as islands
• Not marking visited cells properly

4. Identify the bug in the following DFS code for counting islands and select the correct fix:

void DFS(int r, int c, char[][] grid, bool[][] visited) {
  if (r < 0 || r >= grid.Length || c < 0 || c >= grid[0].Length || grid[r][c] == '0')
    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);
}

int CountIslands(char[][] grid) {
  int count = 0;
  int rows = grid.Length;
  int cols = grid[0].Length;
  bool[][] visited = new bool[rows][];
  for (int i = 0; i < rows; i++) visited[i] = new bool[cols];

  for (int r = 0; r < rows; r++) {
    for (int c = 0; c < cols; c++) {
      if (grid[r][c] == '1' && !visited[r][c]) {
        DFS(r, c, grid, visited);
        count++;
      }
    }
  }
  return count;
}

medium

A. Change grid[r][c] == '0' to grid[r][c] == '1' in base case

B. Add a check for visited[r][c] before recursive DFS calls

C. Initialize visited array with 'true' instead of 'false'

D. Remove visited array and rely on grid modification

Solution

1. Step 1: Identify missing visited check in DFS

   The DFS function does not check if a cell is already visited before recursive calls, causing infinite recursion or revisiting.

2. Step 2: Fix by adding visited check before recursion

   Adding "if (visited[r][c]) return;" before marking visited prevents revisiting cells and infinite loops.

3. Final Answer:

   Add a check for visited[r][c] before recursive DFS calls -> Option B

4. Quick Check:

   Prevent revisiting by checking visited before DFS calls [OK]

Hint: Always check visited before DFS recursion to avoid loops [OK]

Common Mistakes:

• Not checking visited before recursion
• Confusing base case conditions
• Modifying grid instead of using visited array

5. You want to modify the Number of Islands solution to count islands considering diagonal connections as well (8 directions). Which change is needed in the BFS or DFS traversal?

hard

A. Add diagonal directions (-1,-1), (-1,1), (1,-1), (1,1) to the direction arrays

B. Only check horizontal neighbors, ignore vertical and diagonal

C. Use a stack instead of a queue for BFS

D. Change grid cells from '1' to '2' when visited

Solution

1. Step 1: Understand connectivity rules

   Original problem connects cells horizontally and vertically (4 directions). To include diagonals, add those directions.

2. Step 2: Modify direction arrays for 8 directions

   Add diagonal moves (-1,-1), (-1,1), (1,-1), (1,1) to dr and dc arrays to explore all neighbors.

3. Final Answer:

   Add diagonal directions (-1,-1), (-1,1), (1,-1), (1,1) to the direction arrays -> Option A

4. Quick Check:

   Include diagonals by adding their directions [OK]

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

Common Mistakes:

• Ignoring diagonal neighbors
• Confusing BFS and DFS data structures
• Changing grid values instead of using visited array