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 situations like counting forest patches or lakes on a satellite image.

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

📋 What You'll Learn

Create a 2D array representing the map with exact values

Create variables for grid dimensions

Implement BFS and DFS functions to explore islands

Count and print the number of islands found by BFS and DFS

💡 Why This Matters

🌍 Real World

Counting islands or connected regions is useful in geography, image processing, and network analysis.

💼 Career

Understanding graph traversal algorithms like BFS and DFS is essential for software engineering, data science, and technical interviews.

1

Create the map grid

Create a 2D character array called grid with 4 rows and 5 columns containing 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

char grid[4][5] = {
    {'1','1','0','0','0'},
    {'1','1','0','0','0'},
    {'0','0','1','0','0'},
    {'0','0','0','1','1'}
};
// Your code here

Hint

Use a 2D array of type char with 4 rows and 5 columns. Fill it exactly as shown.

2

Add grid size variables

Create two integer variables called rows and cols and set them to 4 and 5 respectively.

DSA C

char grid[4][5] = {
    {'1','1','0','0','0'},
    {'1','1','0','0','0'},
    {'0','0','1','0','0'},
    {'0','0','0','1','1'}
};
int rows = 4;
int cols = 5;
// Your code here

Hint

Define two integer variables rows and cols with values 4 and 5.

3

Implement DFS to count islands

Write a function called dfs that takes parameters grid, rows, cols, r, and c. It should mark connected land cells ('1') as visited by changing them to '0' using Depth-First Search. Then, write a function called numIslandsDFS that uses dfs to count islands in grid.

DSA C

char grid[4][5] = {
    {'1','1','0','0','0'},
    {'1','1','0','0','0'},
    {'0','0','1','0','0'},
    {'0','0','0','1','1'}
};
int rows = 4;
int cols = 5;

// Write dfs and numIslandsDFS functions here
// Your code here

Hint

Use recursion to visit all connected land cells and mark them as '0'. Count islands by calling dfs on unvisited land cells.

4

Count islands using BFS and print results

Write a function called numIslandsBFS that counts islands using Breadth-First Search on a copy of grid. Then, in main, print the number of islands found by numIslandsDFS and numIslandsBFS.

DSA C

#include 
#include 

char grid[4][5] = {
    {'1','1','0','0','0'},
    {'1','1','0','0','0'},
    {'0','0','1','0','0'},
    {'0','0','0','1','1'}
};
int rows = 4;
int cols = 5;

void dfs(char grid[4][5], int rows, int cols, int r, int c) {
    if (r = rows || c >= cols || grid[r][c] == '0') {
        return;
    }
    grid[r][c] = '0';
    dfs(grid, rows, cols, r - 1, c);
    dfs(grid, rows, cols, r + 1, c);
    dfs(grid, rows, cols, r, c - 1);
    dfs(grid, rows, cols, r, c + 1);
}

int numIslandsDFS(char grid[4][5], int rows, int cols) {
    int count = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                dfs(grid, rows, cols, r, c);
                count++;
            }
        }
    }
    return count;
}

// Write numIslandsBFS and main functions below
// Your code here

Hint

Use a queue to implement BFS. Copy the grid before BFS to avoid modifying the original. Print the counts from both methods.