Find the total number of islands using DFS | Faceprep

Program to find the total number of islands using DFS is discussed here. Given an input island matrix, where 0 represents water and 1 represents land. Find the total number of islands that are formed by connected 1’s.

For example, consider the input island matrix 

1 0 1 0
0 0 1 0 0
0 0 1 1 0
0 1 0 1
1 1 1 0 0
0 0 0 0 1
0 1 0 1 0
0 0 1 1 0
0 0 0 1 1
1 1 0 0 0

Total number of islands = 5

total number of islands using dfs

Algorithm to find the number of islands using DFS

  1. Input the island matrix.
  2. Traverse the entire matrix.
  3. Whenever you find “1” use DFS to find all the connected ones in the 8 direction.
  4. Change them to “0” to indicate that this element is traversed and increase the island count by 1.
  5. Return count.

Program to find the number of islands using DFS is given below.

/* C program to find the number of islands using DFS */
#include

/*checks whether the given index is out of the array. Out of array is considered as 0 */
int isSafe(int N,int M,int i,int j)
{
if(i < 0 || i >= N)
return 0;
if(j < 0 || j >= M)
return 0;
return 1;
}

/* this function does the DFS for every new one “1” found and assign every connected one to zero */
void delIsland(int **A,int N,int M,int i,int j)
{
if(isSafe(N,M,i,j) && A[i][j] == 1)
{
A[i][j] = 0;
delIsland(A, N , M , i-1, j-1);
delIsland(A, N, M, i-1, j);
delIsland(A, N, M, i-1, j+1);
delIsland(A, N, M, i, j-1);
delIsland(A, N, M, i, j+1);
delIsland(A, N, M, i+1, j-1);
delIsland(A, N, M, i+1, j);
delIsland(A, N, M, i+1, j+1);
}
}

/* this function finds the total number of islands and return count – 1 as total number of bridges */
int TotalBridge(int **A, int N, int M)
{
int count = 0 ;
int i,j;
for(i=0;i<N;i++)
{
for(j=0;j<M;j++)
if(A[i][j] == 1)
{
count++;
delIsland(A,N,M,i,j);
}
}

if(count == 0)
return 0;
return count;
}

/* get the input and calls the function */
int main()
{
int N,M;
int i,j;
printf(“\nEnter the order of the islands : “);
scanf(“%d %d”, &N,&M);

int **A = (int **)malloc(N * sizeof(int *));
for (i = 0; i < N; i++)
A[i] = (int *)malloc(M * sizeof(int));

printf(“\nEnter the island matrix : \n”);
for(i = 0; i < N ; i++)
for(j = 0; j < M; j++)
scanf(“%d”,&A[i][j]);
printf(“\nTotal Number of islands : %d\n”, TotalBridge(A,N,M));
return 0;
}

// C++ program to find the number of islands using DFS
#include <bits/stdc++.h>
using namespace std;

//checks whether the given index is out of the array. Out of array is considered as 0.
bool isSafe(int N,int M,int i,int j)
{
if(i < 0 || i >= N)
return false;
if(j < 0 || j >= M)
return false;
return true;
}

//this function does the DFS for every new one “1” found and assign every connected one to zero.
void delIsland(int **A,int N,int M,int i,int j)
{
if(isSafe(N,M,i,j) && A[i][j] == 1)
{
A[i][j] = 0;
delIsland(A, N , M , i-1, j-1);
delIsland(A, N, M, i-1, j);
delIsland(A, N, M, i-1, j+1);
delIsland(A, N, M, i, j-1);
delIsland(A, N, M, i, j+1);
delIsland(A, N, M, i+1, j-1);
delIsland(A, N, M, i+1, j);
delIsland(A, N, M, i+1, j+1);
}
}

//this function finds the total number of islands and return count – 1 as total number of bridges
int TotalBridge(int **A, int N, int M)
{
int count = 0 ;
for(int i=0;i<N;i++)
{
for(int j=0;j<M;j++)
if(A[i][j] == 1)
{
count++;
delIsland(A,N,M,i,j);
}
}

if(count == 0)
return 0;
return count;
}

//get the input and calls the function
int main()
{
int N,M;
cout << “\nEnter the order of the islands : “;
cin >> N >> M;

int **A = (int **)malloc(N * sizeof(int *));
for (int i = 0; i < N; i++)
A[i] = (int *)malloc(M * sizeof(int));

cout << “\nEnter the island matrix : \n”;
for(int i = 0; i < N ; i++)
for(int j = 0; j < M; j++)
cin >> A[i][j];
cout << “Total Number of islands : ” << TotalBridge(A,N,M)<<endl;
return 0;
}