Java Program for Find the number of islands | Set 1 (Using DFS)
Given a boolean 2D matrix, find the number of islands. A group of connected 1s forms an island. For example, the below matrix contains 5 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, 1} Output : 5
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.
Below is the implementation of the above approach:
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 |
Number of islands is: 5
Time complexity: O(m x n), where m and n are the numbers of rows and columns of the given matrix respectively.
Auxiliary Space: O(m x n), for creating a visited array of size m * n.
Please refer complete article on Find the number of islands | Set 1 (Using DFS) for more details!
Contact Us