Find the number of islands using DFS

Last Updated : 01 Aug, 2023

Given a binary 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 4 islands.

Example:

Input: mat[][] = {{1, 1, 0, 0, 0},
{0, 1, 0, 0, 1},
{1, 0, 0, 1, 1},
{0, 0, 0, 0, 0},
{1, 0, 1, 0, 0}}
Output: 4

This is a variation of the standard problem: “Counting the number of connected components in an undirected graph”.

Before we go to the problem, let us understand what is a connected component. A connected component of an undirected graph is a subgraph in which every two vertices are connected to each other by a path(s), and which is connected to no other vertices outside the subgraph.
For example, the graph shown below has three connected components.

A graph where all vertices are connected with each other has exactly one connected component, consisting of the whole graph. Such a graph with only one connected component is called a Strongly Connected Graph.
This problem can be easily solved by applying DFS() on each component. In each DFS() call, a component or a sub-graph is visited. We will call DFS on the next un-visited component. The number of calls to DFS() gives the number of connected components. BFS can also be used.

What is an island?
A group of connected 1s forms an island. For example, the below matrix contains 4 islands

Finding the number of islands using an additional Matrix:

The idea is to keep an additional matrix to keep track of the visited nodes in the given matrix, and perform DFS to find the total number of islands

Follow the steps below to solve the problem:

Initialize a boolean matrix visited of the size of the given matrix to false.
Initialize count = 0, to store the answer.
Traverse a loop from 0 till ROW
- Traverse a nested loop from 0 to COL
  - If the value of the current cell in the given matrix is 1 and is not visited
    - Call DFS function
      - Initialize rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 } and colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 } for the neighbour cells.
      - Mark the current cell as visited
      - Run a loop from 0 till 8 to traverse the neighbor
        
        If the neighbor is safe to visit and is not visited
        
        Call DFS recursively on the neighbor.
    - Increment count by 1
Return count as the final answer.

Below is the code implementation of the above approach:

C++

// C++ Program to count islands in boolean 2D matrix
#include <bits/stdc++.h>
using namespace std;
 
#define ROW 5
#define COL 5
 
// A function to check if a given
// cell (row, col) can be included in DFS
int isSafe(int M[][COL], int row, int col,
           bool visited[][COL])
{
    // row number is in range, column
    // number is in range and value is 1
    // and not yet visited
    return (row >= 0) && (row < ROW) && (col >= 0)
           && (col < COL)
           && (M[row][col] && !visited[row][col]);
}
 
// A utility function to do DFS for a
// 2D boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(int M[][COL], int row, int col,
         bool visited[][COL])
{
    // These arrays are used to get
    // row and column numbers of 8
    // neighbours of a given cell
    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
    // Mark this cell as visited
    visited[row][col] = true;
 
    // Recur for all connected neighbours
    for (int k = 0; k < 8; ++k)
        if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                   visited))
            DFS(M, row + rowNbr[k], col + colNbr[k],
                visited);
}
 
// The main function that returns
// count of islands in a given boolean
// 2D matrix
int countIslands(int M[][COL])
{
    // Make a bool array to mark visited cells.
    // Initially all cells are unvisited
    bool visited[ROW][COL];
    memset(visited, 0, sizeof(visited));
 
    // Initialize count as 0 and
    // traverse through the all cells of
    // given matrix
    int count = 0;
    for (int i = 0; i < ROW; ++i)
        for (int j = 0; j < COL; ++j)
 
            // If a cell with value 1 is not
            if (M[i][j] && !visited[i][j]) {
                // visited yet, then new island found
                // Visit all cells in this island.
                DFS(M, i, j, visited);
 
                // and increment island count
                ++count;
            }
 
    return count;
}
 
// Driver code
int main()
{
    int M[][COL] = { { 1, 1, 0, 0, 0 },
                     { 0, 1, 0, 0, 1 },
                     { 1, 0, 0, 1, 1 },
                     { 0, 0, 0, 0, 0 },
                     { 1, 0, 1, 0, 1 } };
 
    cout << "Number of islands is: " << countIslands(M);
 
    return 0;
}
 
// This is code is contributed by rathbhupendra

C

// Program to count islands in boolean 2D matrix
#include <stdbool.h>
#include <stdio.h>
#include <string.h>
 
#define ROW 5
#define COL 5
 
// A function to check if a given cell (row, col) can be
// included in DFS
int isSafe(int M[][COL], int row, int col,
           bool visited[][COL])
{
    // row number is in range, column number is in range and
    // value is 1 and not yet visited
    return (row >= 0) && (row < ROW) && (col >= 0)
           && (col < COL)
           && (M[row][col] && !visited[row][col]);
}
 
// A utility function to do DFS for a 2D boolean matrix. It
// only considers the 8 neighbours as adjacent vertices
void DFS(int M[][COL], int row, int col,
         bool visited[][COL])
{
    // These arrays are used to get row and column numbers
    // of 8 neighbours of a given cell
    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
    // Mark this cell as visited
    visited[row][col] = true;
 
    // Recur for all connected neighbours
    for (int k = 0; k < 8; ++k)
        if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                   visited))
            DFS(M, row + rowNbr[k], col + colNbr[k],
                visited);
}
 
// The main function that returns count of islands in a
// given boolean 2D matrix
int countIslands(int M[][COL])
{
    // Make a bool array to mark visited cells.
    // Initially all cells are unvisited
    bool visited[ROW][COL];
    memset(visited, 0, sizeof(visited));
 
    // Initialize count as 0 and traverse through the all
    // cells of given matrix
    int count = 0;
    for (int i = 0; i < ROW; ++i)
        for (int j = 0; j < COL; ++j)
            if (M[i][j] && !visited[i][j]) // If a cell with
                                           // value 1 is not
            { // visited yet, then new island found
                DFS(M, i, j, visited); // Visit all cells in
                                       // this island.
                ++count; // and increment island count
            }
 
    return count;
}
 
// Driver program to test above function
int main()
{
    int M[][COL] = { { 1, 1, 0, 0, 0 },
                     { 0, 1, 0, 0, 1 },
                     { 1, 0, 0, 1, 1 },
                     { 0, 0, 0, 0, 0 },
                     { 1, 0, 1, 0, 1 } };
 
    printf("Number of islands is: %d\n", countIslands(M));
 
    return 0;
}

Java

// Java program to count islands in boolean 2D matrix
import java.io.*;
import java.lang.*;
import java.util.*;
 
class Islands {
    // No of rows and columns
    static final int ROW = 5, COL = 5;
 
    // A function to check if a given cell (row, col) can
    // be included in DFS
    boolean isSafe(int M[][], int row, int col,
                   boolean visited[][])
    {
        // row number is in range, column number is in range
        // and value is 1 and not yet visited
        return (row >= 0) && (row < ROW) && (col >= 0)
            && (col < COL)
            && (M[row][col] == 1 && !visited[row][col]);
    }
 
    // A utility function to do DFS for a 2D boolean matrix.
    // It only considers the 8 neighbors as adjacent
    // vertices
    void DFS(int M[][], int row, int col,
             boolean visited[][])
    {
        // These arrays are used to get row and column
        // numbers of 8 neighbors of a given cell
        int rowNbr[]
            = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
        int colNbr[]
            = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
 
        // Mark this cell as visited
        visited[row][col] = true;
 
        // Recur for all connected neighbours
        for (int k = 0; k < 8; ++k)
            if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                       visited))
                DFS(M, row + rowNbr[k], col + colNbr[k],
                    visited);
    }
 
    // The main function that returns count of islands in a
    // given boolean 2D matrix
    int countIslands(int M[][])
    {
        // Make a bool array to mark visited cells.
        // Initially all cells are unvisited
        boolean visited[][] = new boolean[ROW][COL];
 
        // Initialize count as 0 and traverse through the
        // all cells of given matrix
        int count = 0;
        for (int i = 0; i < ROW; ++i)
            for (int j = 0; j < COL; ++j)
                if (M[i][j] == 1
                    && !visited[i][j]) // If a cell with
                { // value 1 is not
                    // visited yet, then new island found,
                    // Visit all cells in this island and
                    // increment island count
                    DFS(M, i, j, visited);
                    ++count;
                }
 
        return count;
    }
 
    // Driver method
    public static void main(String[] args)
        throws java.lang.Exception
    {
        int M[][] = new int[][] { { 1, 1, 0, 0, 0 },
                                  { 0, 1, 0, 0, 1 },
                                  { 1, 0, 0, 1, 1 },
                                  { 0, 0, 0, 0, 0 },
                                  { 1, 0, 1, 0, 1 } };
        Islands I = new Islands();
        System.out.println("Number of islands is: "
                           + I.countIslands(M));
    }
} // Contributed by Aakash Hasija

Python3

# Program to count islands in boolean 2D matrix
class Graph:
 
    def __init__(self, row, col, g):
        self.ROW = row
        self.COL = col
        self.graph = g
 
    # A function to check if a given cell
    # (row, col) can be included in DFS
    def isSafe(self, i, j, visited):
        # row number is in range, column number
        # is in range and value is 1
        # and not yet visited
        return (i >= 0 and i < self.ROW and
                j >= 0 and j < self.COL and
                not visited[i][j] and self.graph[i][j])
 
    # A utility function to do DFS for a 2D
    # boolean matrix. It only considers
    # the 8 neighbours as adjacent vertices
 
    def DFS(self, i, j, visited):
 
        # These arrays are used to get row and
        # column numbers of 8 neighbours
        # of a given cell
        rowNbr = [-1, -1, -1,  0, 0,  1, 1, 1]
        colNbr = [-1,  0,  1, -1, 1, -1, 0, 1]
 
        # Mark this cell as visited
        visited[i][j] = True
 
        # Recur for all connected neighbours
        for k in range(8):
            if self.isSafe(i + rowNbr[k], j + colNbr[k], visited):
                self.DFS(i + rowNbr[k], j + colNbr[k], visited)
 
    # The main function that returns
    # count of islands in a given boolean
    # 2D matrix
 
    def countIslands(self):
        # Make a bool array to mark visited cells.
        # Initially all cells are unvisited
        visited = [[False for j in range(self.COL)]for i in range(self.ROW)]
 
        # Initialize count as 0 and traverse
        # through the all cells of
        # given matrix
        count = 0
        for i in range(self.ROW):
            for j in range(self.COL):
                # If a cell with value 1 is not visited yet,
                # then new island found
                if visited[i][j] == False and self.graph[i][j] == 1:
                    # Visit all cells in this island
                    # and increment island count
                    self.DFS(i, j, visited)
                    count += 1
 
        return count
 
 
graph = [[1, 1, 0, 0, 0],
         [0, 1, 0, 0, 1],
         [1, 0, 0, 1, 1],
         [0, 0, 0, 0, 0],
         [1, 0, 1, 0, 1]]
 
 
row = len(graph)
col = len(graph[0])
 
g = Graph(row, col, graph)
 
print("Number of islands is:")
print(g.countIslands())
 
# This code is contributed by Neelam Yadav

C#

// C# program to count
// islands in boolean
// 2D matrix
using System;
 
class GFG {
    // No of rows
    // and columns
    static int ROW = 5, COL = 5;
 
    // A function to check if
    // a given cell (row, col)
    // can be included in DFS
    static bool isSafe(int[, ] M, int row, int col,
                       bool[, ] visited)
    {
        // row number is in range,
        // column number is in range
        // and value is 1 and not
        // yet visited
        return (row >= 0) && (row < ROW) && (col >= 0)
            && (col < COL)
            && (M[row, col] == 1 && !visited[row, col]);
    }
 
    // A utility function to do
    // DFS for a 2D boolean matrix.
    // It only considers the 8
    // neighbors as adjacent vertices
    static void DFS(int[, ] M, int row, int col,
                    bool[, ] visited)
    {
        // These arrays are used to
        // get row and column numbers
        // of 8 neighbors of a given cell
        int[] rowNbr
            = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };
        int[] colNbr
            = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };
 
        // Mark this cell
        // as visited
        visited[row, col] = true;
 
        // Recur for all
        // connected neighbours
        for (int k = 0; k < 8; ++k)
            if (isSafe(M, row + rowNbr[k], col + colNbr[k],
                       visited))
                DFS(M, row + rowNbr[k], col + colNbr[k],
                    visited);
    }
 
    // The main function that
    // returns count of islands
    // in a given boolean 2D matrix
    static int countIslands(int[, ] M)
    {
        // Make a bool array to
        // mark visited cells.
        // Initially all cells
        // are unvisited
        bool[, ] visited = new bool[ROW, COL];
 
        // Initialize count as 0 and
        // traverse through the all
        // cells of given matrix
        int count = 0;
        for (int i = 0; i < ROW; ++i)
            for (int j = 0; j < COL; ++j)
                if (M[i, j] == 1 && !visited[i, j]) {
                    // If a cell with value 1 is not
                    // visited yet, then new island
                    // found, Visit all cells in this
                    // island and increment island count
                    DFS(M, i, j, visited);
                    ++count;
                }
 
        return count;
    }
 
    // Driver Code
    public static void Main()
    {
        int[, ] M = new int[, ] { { 1, 1, 0, 0, 0 },
                                  { 0, 1, 0, 0, 1 },
                                  { 1, 0, 0, 1, 1 },
                                  { 0, 0, 0, 0, 0 },
                                  { 1, 0, 1, 0, 1 } };
        Console.Write("Number of islands is: "
                      + countIslands(M));
    }
}
 
// This code is contributed
// by shiv_bhakt.

Javascript

<script>
// Javascript program to count islands in boolean 2D matrix    
 
    // No of rows and columns
    let  ROW = 5, COL = 5;
     
    // A function to check if a given cell (row, col) can
    // be included in DFS
    function isSafe(M,row,col,visited)
    {
     
        // row number is in range, column number is in range
        // and value is 1 and not yet visited
        return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);
    }
     
    // A utility function to do DFS for a 2D boolean matrix.
    // It only considers the 8 neighbors as adjacent vertices
    function DFS(M, row, col, visited)
    {
        // These arrays are used to get row and column numbers
        // of 8 neighbors of a given cell
        let rowNbr = [-1, -1, -1, 0, 0, 1, 1, 1];
        let colNbr = [-1, 0, 1, -1, 1, -1, 0, 1];
         
        // Mark this cell as visited
        visited[row][col] = true;
         
        // Recur for all connected neighbours
        for (let k = 0; k < 8; ++k)
        {
            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))
            {
                DFS(M, row + rowNbr[k], col + colNbr[k], visited);
            }
        }
         
    }
     
    // The main function that returns count of islands in a given
    // boolean 2D matrix
    function countIslands(M)
    {
        // Make a bool array to mark visited cells.
        // Initially all cells are unvisited
        let visited = new Array(ROW);
        for(let i = 0; i < ROW; i++)
        {
            visited[i] = new Array(COL);
        }
        for(let i = 0; i < ROW; i++)
        {
            for(let j = 0; j < COL; j++)
            {
                visited[i][j] = false;
            }
        }
        // Initialize count as 0 and traverse through the all cells
        // of given matrix
        let count = 0;
        for (let i = 0; i < ROW; ++i)
        {
            for (let j = 0; j < COL; ++j)
            {
                if (M[i][j] == 1 && !visited[i][j])
                {
                    // value 1 is not
                    // visited yet, then new island found, Visit all
                    // cells in this island and increment island count
                    DFS(M, i, j, visited);
                    count++;
                }
            }
        }
        return count;
    }
     
    // Driver method
    let M = [[ 1, 1, 0, 0, 0 ], [ 0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1] ,[0, 0, 0, 0, 0], [1, 0, 1, 0, 1]];
    document.write("Number of islands is: " + countIslands(M));
     
    // This code is contributed by avanitrachhadiya2155
</script>

PHP

<?php 
// Program to count islands 
// in boolean 2D matrix
 
$ROW = 5;
$COL = 5;
 
// A function to check if a 
// given cell (row, col) can 
// be included in DFS
function isSafe(&$M, $row, $col,
                &$visited)
{
    global $ROW, $COL;
     
    // row number is in range,
    // column number is in 
    // range and value is 1 
    // and not yet visited
    return ($row >= 0) && ($row < $ROW) &&     
           ($col >= 0) && ($col < $COL) &&     
           ($M[$row][$col] && 
             !isset($visited[$row][$col])); 
}
 
// A utility function to do DFS
// for a 2D boolean matrix. It 
// only considers the 8 neighbours
// as adjacent vertices
function DFS(&$M, $row, $col,
            &$visited)
{
    // These arrays are used to
    // get row and column numbers 
    // of 8 neighbours of a given cell
    $rowNbr = array(-1, -1, -1, 0, 
                    0, 1, 1, 1);
    $colNbr = array(-1, 0, 1, -1, 
                    1, -1, 0, 1);
 
    // Mark this cell as visited
    $visited[$row][$col] = true;
 
    // Recur for all 
    // connected neighbours
    for ($k = 0; $k < 8; ++$k)
        if (isSafe($M, $row + $rowNbr[$k], 
                $col + $colNbr[$k], $visited))
            DFS($M, $row + $rowNbr[$k], 
                $col + $colNbr[$k], $visited);
}
 
// The main function that returns
// count of islands in a given 
// boolean 2D matrix
function countIslands(&$M)
{
    global $ROW, $COL;
     
    // Make a bool array to 
    // mark visited cells. 
    // Initially all cells 
    // are unvisited
    $visited = array(array());
 
    // Initialize count as 0 and
    // traverse through the all 
    // cells of given matrix
    $count = 0;
    for ($i = 0; $i < $ROW; ++$i)
        for ($j = 0; $j < $COL; ++$j)
            if ($M[$i][$j] && 
                 !isset($visited[$i][$j])) // If a cell with value 1
            {                               // is not visited yet, 
                DFS($M, $i, $j, $visited); // then new island found 
                ++$count;                   // Visit all cells in this 
            }                               // island and increment 
                                           // island count.
 
    return $count;
}
 
// Driver Code
$M = array(array(1, 1, 0, 0, 0),
           array(0, 1, 0, 0, 1),
           array(1, 0, 0, 1, 1),
            array(0, 0, 0, 0, 0),
           array(1, 0, 1, 0, 1));
 
echo "Number of islands is: ",
            countIslands($M);
 
// This code is contributed 
// by ChitraNayal 
?>

Output

Number of islands is: 5

Time complexity: O(ROW x COL), where ROW is the number of rows and COL is the number of columns in the given matrix.
Auxiliary Space: O(ROW x COL), for creating an additional visited matrix.

Finding the number of islands using DFS:

The idea is to modify the given matrix, and perform DFS to find the total number of islands

Follow the steps below to solve the problem:

Initialize count = 0, to store the answer.
Traverse a loop from 0 till ROW
- Traverse a nested loop from 0 to COL
  - If the value of the current cell in the given matrix is 1
    - Increment count by 1
    - Call DFS function
      - If the cell exceeds the boundary or the value at the current cell is 0
        
        Return.
      - Update the value at the current cell as 0.
      - Call DFS on the neighbor recursively
Return count as the final answer.

Below is the code implementation of the above approach:

C++

// C++Program to count islands in boolean 2D matrix
#include <bits/stdc++.h>
using namespace std;
 
// A utility function to do DFS for a 2D
//  boolean matrix. It only considers
// the 8 neighbours as adjacent vertices
void DFS(vector<vector<int> >& M, int i, int j, int ROW,
         int COL)
{
    // Base condition
    // if i less than 0 or j less than 0 or i greater than
    // ROW-1 or j greater than COL-  or if M[i][j] != 1 then
    // we will simply return
    if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1)
        || M[i][j] != 1) {
        return;
    }
 
    if (M[i][j] == 1) {
        M[i][j] = 0;
        DFS(M, i + 1, j, ROW, COL); // right side traversal
        DFS(M, i - 1, j, ROW, COL); // left side traversal
        DFS(M, i, j + 1, ROW, COL); // upward side traversal
        DFS(M, i, j - 1, ROW,
            COL); // downward side traversal
        DFS(M, i + 1, j + 1, ROW,
            COL); // upward-right side traversal
        DFS(M, i - 1, j - 1, ROW,
            COL); // downward-left side traversal
        DFS(M, i + 1, j - 1, ROW,
            COL); // downward-right side traversal
        DFS(M, i - 1, j + 1, ROW,
            COL); // upward-left side traversal
    }
}
 
int countIslands(vector<vector<int> >& M)
{
    int ROW = M.size();
    int COL = M[0].size();
    int count = 0;
    for (int i = 0; i < ROW; i++) {
        for (int j = 0; j < COL; j++) {
            if (M[i][j] == 1) {
                count++;
                DFS(M, i, j, ROW, COL); // traversal starts
                                        // from current cell
            }
        }
    }
    return count;
}
 
// Driver Code
int main()
{
    vector<vector<int> > M = { { 1, 1, 0, 0, 0 },
                               { 0, 1, 0, 0, 1 },
                               { 1, 0, 0, 1, 1 },
                               { 0, 0, 0, 0, 0 },
                               { 1, 0, 1, 0, 1 } };
 
    cout << "Number of islands is: " << countIslands(M);
    return 0;
}
 
// This code is contributed by ajaymakvana.
//    Code improved by Animesh Singh

Java

// Java Program to count islands in boolean 2D matrix
import java.util.*;
public class Main {
    // A utility function to do DFS for a 2D
    //  boolean matrix. It only considers
    // the 8 neighbours as adjacent vertices
    static void DFS(int[][] M, int i, int j, int ROW,
                    int COL)
    {
 
        // Base condition
        // if i less than 0 or j less than 0 or i greater
        // than ROW-1 or j greater than COL-  or if M[i][j]
        // != 1 then we will simply return
        if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1)
            || M[i][j] != 1) {
            return;
        }
 
        if (M[i][j] == 1) {
            M[i][j] = 0;
            DFS(M, i + 1, j, ROW,
                COL); // right side traversal
            DFS(M, i - 1, j, ROW,
                COL); // left side traversal
            DFS(M, i, j + 1, ROW,
                COL); // upward side traversal
            DFS(M, i, j - 1, ROW,
                COL); // downward side traversal
            DFS(M, i + 1, j + 1, ROW,
                COL); // upward-right side traversal
            DFS(M, i - 1, j - 1, ROW,
                COL); // downward-left side traversal
            DFS(M, i + 1, j - 1, ROW,
                COL); // downward-right side traversal
            DFS(M, i - 1, j + 1, ROW,
                COL); // upward-left side traversal
        }
    }
 
    static int countIslands(int[][] M)
    {
        int ROW = M.length;
        int COL = M[0].length;
        int count = 0;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                if (M[i][j] == 1) {
                    count++;
                    DFS(M, i, j, ROW,
                        COL); // traversal starts from
                              // current cell
                }
            }
        }
        return count;
    }
 
    // Driver code
    public static void main(String[] args)
    {
        int[][] M = { { 1, 1, 0, 0, 0 },
                      { 0, 1, 0, 0, 1 },
                      { 1, 0, 0, 1, 1 },
                      { 0, 0, 0, 0, 0 },
                      { 1, 0, 1, 0, 1 } };
 
        System.out.print("Number of islands is: "
                         + countIslands(M));
    }
}
 
// This code is contributed by suresh07.
// Code improved by Animesh Singh

Python3

# Program to count islands in boolean 2D matrix
class Graph:
 
    def __init__(self, row, col, graph):
        self.ROW = row
        self.COL = col
        self.graph = graph
 
    # A utility function to do DFS for a 2D
    # boolean matrix. It only considers
    # the 8 neighbours as adjacent vertices
    def DFS(self, i, j):
        if i < 0 or i >= len(self.graph) or j < 0 or j >= len(self.graph[0]) or self.graph[i][j] != 1:
            return
 
        # mark it as visited
        self.graph[i][j] = -1
 
        # Recur for 8 neighbours
        self.DFS(i - 1, j - 1)
        self.DFS(i - 1, j)
        self.DFS(i - 1, j + 1)
        self.DFS(i, j - 1)
        self.DFS(i, j + 1)
        self.DFS(i + 1, j - 1)
        self.DFS(i + 1, j)
        self.DFS(i + 1, j + 1)
 
    # The main function that returns
    # count of islands in a given boolean
    # 2D matrix
    def countIslands(self):
        # Initialize count as 0 and traverse
        # through the all cells of
        # given matrix
        count = 0
        for i in range(self.ROW):
            for j in range(self.COL):
                # If a cell with value 1 is not visited yet,
                # then new island found
                if self.graph[i][j] == 1:
                    # Visit all cells in this island
                    # and increment island count
                    self.DFS(i, j)
                    count += 1
 
        return count
 
 
graph = [
    [1, 1, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [1, 0, 1, 0, 1]
]
 
 
row = len(graph)
col = len(graph[0])
 
g = Graph(row, col, graph)
 
print("Number of islands is:", g.countIslands())
 
# This code is contributed by Shivam Shrey

C#

// C# Program to count islands in boolean 2D matrix
using System;
using System.Collections.Generic;
class GFG {
 
    // A utility function to do DFS for a 2D
    //  boolean matrix. It only considers
    // the 8 neighbours as adjacent vertices
    static void DFS(int[, ] M, int i, int j, int ROW,
                    int COL)
    {
 
        // Base condition
        // if i less than 0 or j less than 0 or i greater
        // than ROW-1 or j greater than COL-  or if M[i][j]
        // != 1 then we will simply return
        if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1)
            || M[i, j] != 1) {
            return;
        }
 
        if (M[i, j] == 1) {
            M[i, j] = 0;
            DFS(M, i + 1, j, ROW,
                COL); // right side traversal
            DFS(M, i - 1, j, ROW,
                COL); // left side traversal
            DFS(M, i, j + 1, ROW,
                COL); // upward side traversal
            DFS(M, i, j - 1, ROW,
                COL); // downward side traversal
            DFS(M, i + 1, j + 1, ROW,
                COL); // upward-right side traversal
            DFS(M, i - 1, j - 1, ROW,
                COL); // downward-left side traversal
            DFS(M, i + 1, j - 1, ROW,
                COL); // downward-right side traversal
            DFS(M, i - 1, j + 1, ROW,
                COL); // upward-left side traversal
        }
    }
 
    static int countIslands(int[, ] M)
    {
        int ROW = M.GetLength(0);
        int COL = M.GetLength(1);
        int count = 0;
        for (int i = 0; i < ROW; i++) {
            for (int j = 0; j < COL; j++) {
                if (M[i, j] == 1) {
                    count++;
                    DFS(M, i, j, ROW,
                        COL); // traversal starts from
                              // current cell
                }
            }
        }
        return count;
    }
 
    // Driver code
    static void Main()
    {
        int[, ] M = { { 1, 1, 0, 0, 0 },
                      { 0, 1, 0, 0, 1 },
                      { 1, 0, 0, 1, 1 },
                      { 0, 0, 0, 0, 0 },
                      { 1, 0, 1, 0, 1 } };
 
        Console.Write("Number of islands is: "
                      + countIslands(M));
    }
}
 
// This code is contributed by decode2207.
// Code improved by Animesh Singh

Javascript

<script>
    // Javascript Program to count islands in boolean 2D matrix
     
    // A utility function to do DFS for a 2D
    //  boolean matrix. It only considers
    // the 8 neighbours as adjacent vertices
    function DFS(M, i, j, ROW, COL)
    {
        // Base condition
        // if i less than 0 or j less than 0 or i greater than ROW-1 or j greater than COL-  or if M[i][j] != 1 then we will simply return
        if (i < 0 || j < 0 || i > (ROW - 1) || j > (COL - 1) || M[i][j] != 1)
        {
            return;
        }
 
        if (M[i][j] == 1)
        {
            M[i][j] = 0;
            DFS(M, i + 1, j, ROW, COL);     //right side traversal
            DFS(M, i - 1, j, ROW, COL);     //left side traversal
            DFS(M, i, j + 1, ROW, COL);     //upward side traversal
            DFS(M, i, j - 1, ROW, COL);     //downward side traversal
            DFS(M, i + 1, j + 1, ROW, COL); //upward-right side traversal
            DFS(M, i - 1, j - 1, ROW, COL); //downward-left side traversal
            DFS(M, i + 1, j - 1, ROW, COL); //downward-right side traversal
            DFS(M, i - 1, j + 1, ROW, COL); //upward-left side traversal
        }
    }
 
    function countIslands(M)
    {
        let ROW = M.length;
        let COL = M[0].length;
        let count = 0;
        for (let i = 0; i < ROW; i++)
        {
            for (let j = 0; j < COL; j++)
            {
                if (M[i][j] == 1)
                {
                    count++;
                    DFS(M, i, j, ROW, COL); //traversal starts from current cell
                }
            }
        }
        return count;
    }
     
    let M = [[1, 1, 0, 0, 0],
             [0, 1, 0, 0, 1],
             [1, 0, 0, 1, 1],
             [0, 0, 0, 0, 0],
             [1, 0, 1, 0, 1]];
  
    document.write("Number of islands is: " + countIslands(M));
     
    // This code is contributed by divyesh072019.
    //    Code improved by Animesh Singh
</script>

Output

Number of islands is: 5

Time complexity: O(ROW x COL), where ROW is the number of rows and COL is the number of columns in the given matrix.
Auxiliary Space: O(ROW * COL), as to do DFS we need extra auxiliary stack space.

Using Extra O(n*m) Space:

Approach:

In this approach we are traversing over matrix and if the current element is equal to one and not visited already than we mark all connect(mark visit) element/point as visited and increment count (cnt) by one.

C++14

#include <iostream>
#include<bits/stdc++.h>
using namespace std;
 
int n,m;
//valid row and column checker.
bool check(int i,int j){
  return i>=0&&j>=0&&i<n&&j<m;
}
 
void mark_component(vector<vector<int>>&v,vector<vector<bool>>&vis,int i,int j){
   if(!check(i,j))return;
   vis[i][j]=1;
   //marking(connecting all possible part of single island.
   if (v[i][j] == 1) {
        v[i][j] = 0;
        mark_component(v,vis,i+1,j);
        mark_component(v,vis,i-1,j);
        mark_component(v,vis,i,j+1);
        mark_component(v,vis,i,j-1);
        mark_component(v,vis,i+1,j+1);
        mark_component(v,vis,i-1,j-1);
        mark_component(v,vis,i+1,j-1); 
        mark_component(v,vis,i-1,j+1);
    }
}
 
int main() {
    vector<vector<int>>v{{ 1, 1, 0, 0, 0 },
                         { 0, 1, 0, 0, 1 },
                         { 1, 0, 0, 1, 1 },
                         { 0, 0, 0, 0, 0 },
                         { 1, 0, 1, 0, 1 }};
    n=v.size();
    m=v[0].size();
   int cnt=0;
  //visit vector.
   vector<vector<bool>>vis(n,vector<bool>(m,0));
   for(int i=0;i<n;i++){
    for(int j=0;j<m;j++){
      if(!vis[i][j]&&v[i][j]==1){
         ++cnt;
         mark_component(v,vis,i,j);
       }
     }
   }
   cout<<"The number of islands in the matrix are :"<<endl;
   cout<<cnt<<endl;
  //code by Sanket Gode
    return 0;
}

Java

import java.io.*;
import java.util.*;
 
class Main {
    static int n, m;
 
    // valid row and column checker
    static boolean check(int i, int j)
    {
        return i >= 0 && j >= 0 && i < n && j < m;
    }
 
    static void mark_component(int[][] v, boolean[][] vis,
                               int i, int j)
    {
        if (!check(i, j))
            return;
        vis[i][j] = true;
        // marking (connecting all possible parts of single
        // island)
        if (v[i][j] == 1) {
            v[i][j] = 0;
            mark_component(v, vis, i + 1, j);
            mark_component(v, vis, i - 1, j);
            mark_component(v, vis, i, j + 1);
            mark_component(v, vis, i, j - 1);
            mark_component(v, vis, i + 1, j + 1);
            mark_component(v, vis, i - 1, j - 1);
            mark_component(v, vis, i + 1, j - 1);
            mark_component(v, vis, i - 1, j + 1);
        }
    }
 
    public static void main(String[] args)
    {
        int[][] v = { { 1, 1, 0, 0, 0 },
                      { 0, 1, 0, 0, 1 },
                      { 1, 0, 0, 1, 1 },
                      { 0, 0, 0, 0, 0 },
                      { 1, 0, 1, 0, 1 } };
        n = v.length;
        m = v[0].length;
        int cnt = 0;
        // visit vector
        boolean[][] vis = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j] && v[i][j] == 1) {
                    ++cnt;
                    mark_component(v, vis, i, j);
                }
            }
        }
        System.out.println(
            "The number of islands in the matrix are: ");
        System.out.println(cnt);
    }
}

Python3

def check(i, j, n, m):
    return i >= 0 and j >= 0 and i < n and j < m
 
def mark_component(v, vis, i, j, n, m):
    if not check(i, j, n, m):
        return
    vis[i][j] = True
    if v[i][j] == 1:
        v[i][j] = 0
#marking(connecting all possible part of single island.
        mark_component(v, vis, i + 1, j, n, m)
        mark_component(v, vis, i - 1, j, n, m)
        mark_component(v, vis, i, j + 1, n, m)
        mark_component(v, vis, i, j - 1, n, m)
        mark_component(v, vis, i + 1, j + 1, n, m)
        mark_component(v, vis, i - 1, j - 1, n, m)
        mark_component(v, vis, i + 1, j - 1, n, m)
        mark_component(v, vis, i - 1, j + 1, n, m)
 
v = [[1, 1, 0, 0, 0],
     [0, 1, 0, 0, 1],
     [1, 0, 0, 1, 1],
     [0, 0, 0, 0, 0],
     [1, 0, 1, 0, 1]]
n = len(v)
m = len(v[0])
cnt = 0
vis = [[False for j in range(m)] for i in range(n)]
for i in range(n):
    for j in range(m):
        if not vis[i][j] and v[i][j] == 1:
            cnt += 1
            mark_component(v, vis, i, j, n, m)
print("The number of islands in the matrix are:")
print(cnt)
# This code is contributed by Shivam Tiwari

C#

using System;
using System.Collections.Generic;
 
class GFG {
    // valid row and column checker
    public static bool check(int i, int j, int n, int m)
    {
        return i >= 0 && j >= 0 && i < n && j < m;
    }
 
    public static void mark_component(List<List<int> > v,
                                      List<List<bool> > vis,
                                      int i, int j)
    {
        int n = v.Count;
        int m = v[0].Count;
 
        if (!check(i, j, n, m))
            return;
        vis[i][j] = true;
        // marking (connecting all possible parts of single
        // island)
        if (v[i][j] == 1) {
            v[i][j] = 0;
            mark_component(v, vis, i + 1, j);
            mark_component(v, vis, i - 1, j);
            mark_component(v, vis, i, j + 1);
            mark_component(v, vis, i, j - 1);
            mark_component(v, vis, i + 1, j + 1);
            mark_component(v, vis, i - 1, j - 1);
            mark_component(v, vis, i + 1, j - 1);
            mark_component(v, vis, i - 1, j + 1);
        }
    }
 
    public static void Main()
    {
        List<List<int> > v = new List<List<int> >{
            new List<int>{ 1, 1, 0, 0, 0 },
            new List<int>{ 0, 1, 0, 0, 1 },
            new List<int>{ 1, 0, 0, 1, 1 },
            new List<int>{ 0, 0, 0, 0, 0 },
            new List<int>{ 1, 0, 1, 0, 1 }
        };
 
        int n = v.Count;
        int m = v[0].Count;
        int cnt = 0;
        // visit vector
        List<List<bool> > vis = new List<List<bool> >();
        for (int i = 0; i < n; i++) {
            vis.Add(new List<bool>());
            for (int j = 0; j < m; j++) {
                vis[i].Add(false);
            }
        }
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (!vis[i][j] && v[i][j] == 1) {
                    cnt++;
                    mark_component(v, vis, i, j);
                }
            }
        }
 
        Console.WriteLine(
            "The number of islands in the matrix are :");
        Console.WriteLine(cnt);
    }
}

Javascript

// JavaScript program to count the number of islands in a given binary matrix
 
// valid row and column checker
function check(i, j, n, m) {
    return i >= 0 && j >= 0 && i < n && j < m;
}
 
// marking (connecting all possible parts of single island)
function mark_component(v, vis, i, j, n, m) {
    if (!check(i, j, n, m))
        return;
    vis[i][j] = true;
    if (v[i][j] == 1) {
        v[i][j] = 0;
        mark_component(v, vis, i + 1, j, n, m);
        mark_component(v, vis, i - 1, j, n, m);
        mark_component(v, vis, i, j + 1, n, m);
        mark_component(v, vis, i, j - 1, n, m);
        mark_component(v, vis, i + 1, j + 1, n, m);
        mark_component(v, vis, i - 1, j - 1, n, m);
        mark_component(v, vis, i + 1, j - 1, n, m);
        mark_component(v, vis, i - 1, j + 1, n, m);
    }
}
 
function countIslands(v) {
    let n = v.length;
    let m = v[0].length;
    let cnt = 0;
    // visit vector
    let vis = new Array(n).fill().map(() => new Array(m).fill(false));
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < m; j++) {
            if (!vis[i][j] && v[i][j] == 1) {
                ++cnt;
                mark_component(v, vis, i, j, n, m);
            }
        }
    }
    console.log("The number of islands in the matrix are: ");
    console.log(cnt);
}
 
// Sample matrix input
let v = [[1, 1, 0, 0, 0],
         [0, 1, 0, 0, 1],
         [1, 0, 0, 1, 1],
         [0, 0, 0, 0, 0],
         [1, 0, 1, 0, 1]];
 
countIslands(v);
// This code is contributed by Shivam Tiwari

Output

The number of islands in the matrix are :
5

Time complexity: O(n*m).
Auxiliary Space: O(n*m).

Find the number of Islands | Set 2 (Using Disjoint Set)
Islands in a graph using BFS

Suggest improvement

Hopcroft–Karp Algorithm for Maximum Matching | Set 2 (Implementation)

Minimum steps to reach a destination

Share your thoughts in the comments

DFS in different language

Variations of DFS implementations

Graph Algorithms that uses DFS

Easy problems on DFS

Medium problems on DFS

Hard problems on DFS

DFS in different language

Variations of DFS implementations

Graph Algorithms that uses DFS

Easy problems on DFS

Medium problems on DFS

Hard problems on DFS

Find the number of islands using DFS

Finding the number of islands using an additional Matrix:

C++

C

Java

Python3

C#

Javascript

PHP

Finding the number of islands using DFS:

C++

Java

Python3

C#

Javascript

C++14

Java

Python3

C#

Javascript

Please Login to comment...

Similar Reads

What kind of Experience do you want to share?