Algotree > Algorithms > Tree & Graph Traversal > Breadth First Search ( BFS ) Algorithm > Finding the number of islands

Finding the number of islands

Problem Statement
You are given a 2D grid, where each cell can be either ‘1’ (land) or ‘0’ (water). In this grid, an island is defined as a group of connected ‘1’s (land) surrounded by ‘0’s (water). Your task is to count the number of distinct islands (groups of connected ‘1’s) there are in the grid.

Finding the number of islands in a 2D grid can be effectively achieved using the Breadth-First Search (BFS) algorithm.

Steps

Create a variable to keep track of the number of islands.
Create a queue to facilitate BFS.
Explore the grid: Using a loop, visit each cell in the grid. When you find a ‘1’, it indicates the start of a new island.

BFS Traversal:

Add the starting cell that has ‘1’ (land) to the queue. This should be an unvisited cell as we are beginning the algorithm.

While the queue is not empty:

Dequeue a cell and explore its neighbors (up, down, left, right).
If any of the neighboring cells are ‘1’, mark them as visited and add them to the queue.

Count islands: Each time you start a BFS from an unvisited ‘1’, increment the island count.

C++ program for finding the number of islands

#include<iostream>
#include<queue>
#include<tuple>

using namespace std;

class Island {

    public:

    // Below function finds the number of islands on a grid
    int GetNumber (vector<vector<char>>& grid) {

        int rows = grid.size();
        int cols = grid[0].size();

        // Assumption is that the grid size is 300 x 300
        bool visited[301][301] = {{ false }};

        queue<tuple<int, int>> Q;

        // For visiting Up, Right, Down and Left
        int dx[4] = { -1, 0, 1, 0 };
        int dy[4] = { 0, 1, 0, -1 };

        int num = 0;

        // Visit all not visited cells of the grid.
        for (int r=0; r<rows; r++) {
            for (int c=0; c<cols; c++) {

                // If a non visited land is found increase the count
                if (grid[r][c] == '1' and !visited[r][c]) {
                    num++;

                    Q.push(make_tuple(r,c));
                    visited[r][c] = true;

                    while (!Q.empty()) {

                        tuple<int,int> pos = Q.front();
                        Q.pop();
                        int x = get<0>(pos);
                        int y = get<1>(pos);

                        // Visit adjacent positions ( Up, Right, Down and Left )
                        for (int i=0; i<4; i++) {
                            int newx = x + dx[i];
                            int newy = y + dy[i];

                            // Check if we are going beyond the grid.
                            if (newx >= 0 and newx < rows and
                                newy >= 0 and newy < cols) {
                                if (grid[newx][newy] == '1' and !visited[newx][newy]) {
                                    Q.push(make_tuple(newx, newy));
                                    visited[newx][newy] = 1;
                                }
                            }
                        }
                    }
                }
            }
        }
        return num;
    }
};

int main () {

    vector<vector<char>> grid = { { '1', '1', '0', '0', '0' },
                                  { '1', '1', '0', '0', '0' },
                                  { '0', '0', '1', '0', '0' },
                                  { '0', '0', '0', '1', '1' } };
    Island I;

    cout << "Number of islands : " << I.GetNumber (grid) << endl;
    return 0;
}

Output

Number of islands : 3