C++ Program To Find The Number Of Islands Using Dfs

A common problem encountered in graph theory and image processing involves the requirement for a C++ program to determine the count of islands through Depth-First Search (DFS). This tutorial will delve into the C++ code for identifying the number of islands utilizing DFS.

Example:

Let's consider an illustration to showcase the process of determining the quantity of islands using Depth First Search (DFS) in C++.

#include <iostream>
#include <vector>
class Solution
{
public:
    int numIslands(std::vector<std::vector<char>>& grid)
    {
        int num = 0;
        // Initialize the number of islands
        // Check for edge cases
        if (grid.empty() || grid[0].empty())
        {
            return 0;
        }
        int rows = grid.size();
        int cols = grid[0].size();
        // Iterate through the entire grid
        for (int i = 0; i < rows; ++i)
        {
            for (int j = 0; j < cols; ++j) 
            {
                if (grid[i][j] == '1')
                {
                    // If we find '1', start a DFS to mark the entire island
                    dfs(grid, i, j);
                    num++;
                }
            }
        }
        return num;
    }
    void dfs(std::vector<std::vector<char>>& grid, int row, int col)
    {
        int rows = grid.size();
        int cols = grid[0].size();
        // Base cases for the DFS recursion
        if (row < 0 || col < 0 || row >= rows || col >= cols || grid[row][col] == '0') 
        {
            return;
        }
        // Mark the current cell as visited (0)
        grid[row][col] = '0';
        // Recursively visit adjacent cells
        dfs(grid, row - 1, col); // Up
        dfs(grid, row + 1, col); // Down
        dfs(grid, row, col - 1); // Left
        dfs(grid, row, col + 1); // Right
    }
};
int main() 
{
    std::vector<std::vector<char>> grid =
    {
        {'1', '1', '0', '0', '0'},
        {'1', '1', '0', '0', '0'},
        {'0', '0', '1', '0', '0'},
        {'0', '0', '0', '1', '1'}
    };
    Solution solution;
    int numIslands = solution.numIslands(grid);
    std::cout << "Number of islands: " << numIslands << std::endl;
    return 0;
}

Output:

Number of islands: 3

Explanation:

1. Solution Class

In this instance, the solution class serves as the key to identifying the quantity of islands within it. The methods numIslands and dfs stand out as the primary strategies encapsulated within this class.

1. numIslands Function

This function is employed to determine the quantity of islands within the binary grid. It takes a binary matrix in the form of a 2D vector grid as an argument. It creates an integer variable named num, which is initialized to 0 to monitor the number of islands.

1. Performing an Edge Case Verification

The edge scenarios of the input grid, such as being devoid of content or containing empty rows, are verified. If either of these situations occurs, the function will yield a result of 0, indicating the absence of any islands.

1. Iterating Through the Grid

In this method, nested iterations are employed to navigate through the entire binary matrix. Both the internal and external loops move through the various columns and rows.

1. Implementing DFS to Explore Islands

In the matrix, the beginning of a new island is indicated by the presence of a "1" (which denotes land) at coordinates (i, j) . After that, the method invokes the dfs method to conduct a Depth-First Search to mark the entire island as visited. It increases the num variable to count the island after marking it.

1. dfs Method

• ✅ The entire island will be marked as visited using this recursive DFS method .
• ✅ The current row and column coordinates are input parameters, together with the binary matrix grid.
• ✅ Base Cases: It verifies base cases to prevent moving outside of boundaries or stopping at cells that are already visited ('0') or are water.
• ✅ If any of these fundamental conditions are true, it simply returns.
• ✅ Adding a visitation mark:
• ✅ The '1' is changed to a '0' , signaling that the current cell has been visited.
• ✅ Recursion: It repeatedly investigates adjacent cells in four directions, up, down, left, and right, to indicate that the entire island has been visited.

1. main Function

The explanation of a given binary matrix (grid) is found within the primary function. Subsequently, an object of the solution class is created. The method numIslands is employed to determine the count of islands. Following this process, the result displays the overall count of islands.

The software displays the count of islands identified within the binary grid.

Complexity:

• ✅ Usually, the time complexity of this algorithm is O(rows * cols), with "rows" representing the matrix rows and "cols" representing the matrix columns. This complexity arises from the necessity to traverse each cell only once.
• ✅ Regarding the recursive Depth-First Search (DFS) approach, the space complexity is O(1) as it doesn't utilize extra data structures. Nevertheless, a larger function call stack may lead to increased storage requirements for extensive inputs.

Conclusion:

In summary, a C++ script for calculating the quantity of islands with Depth-First Search (DFS) proves to be a valuable asset in identifying connected groups of '1's within a binary grid. This script leverages the DFS algorithm to efficiently traverse the matrix and determine the total count of islands.