Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
2.1.
Sample Examples
3.
Brute Force Approach
3.1.
Algorithm
3.2.
Python Implementation
3.3.
Complexity Analysis
4.
Optimized Approach
4.1.
Algorithm
4.2.
C++ Implementation
4.3.
Python Implementation
4.4.
Complexity Analysis
5.
Frequently Asked Questions
5.1.
What is meant by an undirected graph?
5.2.
How do you find the number of connected components on a graph?
5.3.
How does DFS work?
5.4.
How does BFS work?
5.5.
What is a graph?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find Number of Islands

Author Teesha Goyal
0 upvote
Master Power BI using Netflix Data
Speaker
Ashwin Goyal
Product @
18 Jun, 2024 @ 01:30 PM

Introduction

Hello Ninjas! How is your coding preparation going on? I hope it's going well. We are back with another DSA problem. This problem is based on the graph data structure. We already know that the non-linear data structure known as a graph consists of vertices and edges, and it is among the most commonly used data structures these days.

Introduction

In this problem, we are provided an undirected graph in which we are supposed to find the number of islands. We'll discuss the brute force approach to this problem and then further optimize it.

Problem Statement

We are given a boolean 2D matrix as an input representing the undirected graph, and we need to output the total number of islands present in that graph. The graph matrix being boolean, only has two elements, either 0 or 1. In this problem, an island is considered the group of connected 1s. 

If there are some nodes that are linked to each other using some path, then a set of those nodes is known as a connected component of an undirected graph. Or in other words, we can say that a subgraph with every pair of vertices connected to each other by a path (or set of paths) and no connections to any other vertices outside the subgraph is referred to as a connected component of an undirected graph. A graph with every vertex connected to every other vertex has exactly one connected component: the entire graph. A strongly linked graph is one with only one connected component. 

Given below is an image of a sub-graph which is a connected component of an undirected graph.

Connected part of a graph

We can clearly see that every vertex in this graph is connected to every other vertex. Hence this is a connected component of a graph

Sample Examples

Let us consider a graph that is represented as a 2D boolean matrix:

Input

mat[][] = [[1 , 1 , 1 , 0 , 0], 
               [0 , 0 , 0 , 0 , 1], 
               [1 , 0 , 1 , 1 , 1], 
               [0 , 0 , 0 , 0 , 0], 
               [1 , 0 , 1 , 0 , 1]]


Output

For this matrix, the output is 6, i.e., the total number of islands present in this graph is 6. Let's see how.

Explanation

1s at the position (0,0),(0,1), and (0,2) [if we consider 0-indexing], are connected and will be considered as one of the islands. Similarly, 1s at the position (1,4),(2,2),(2,3), and (2,4) is also an island. Similarly, all other islands can be identified in the given 2D graph.

So, a total of 6 islands are present in the given an example.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Brute Force Approach

By using DFS traversal on each component, the problem can be easily and quickly solved. A component is visited every time the DFS() function is called. The DFS function will call the next unvisited component. The number of connected components is determined by how many times DFS() function is called. This question can also be solved using Breadth-First Search(BFS). 

A cell in a 2D matrix has 8 neighbors altogether. In the standard DFS technique, we recursively call all the adjacent vertices. But in this case, we can recursively call for only eight neighbors. To prevent further visits, we keep track of the visited 1s.

Algorithm

  • We will keep track of visited vertices of the graph by creating a matrix named visited_nodes, which stores boolean values for every cell, whether it is visited or not.
     
  • We will make a function that will check whether a particular cell (given the row and column) is in range. Let’s name the function valid_node().
     
  • Another function, dfs (), is created for performing a Depth-First search on a particular node that takes node and graph as its parameters. It only treats the eight nearby vertices as neighboring vertices.
     
  • Inside the dfs() function, Mark the particular cell as visited(i.e., visited[i][j]=True) and perform DFS on all its neighbors.
     
  • The primary function number_of_Islands() in a given boolean 2D matrix that returns the number of islands in that undirected graph is created.
     
  • Initialize a variable named number_of_islands with value 0 and traverse through the entire graph matrix.
     
  • A new island is discovered if a cell with the value 1 has yet to be visited. To increase the island count, visit every cell on this island.

Python Implementation

class Solution:
    def __init__(self):
        self.visited_nodes = []
        
    #function to check whether the cell is in range or not
    
    def valid_node(self, x, y, graph):
        x_range = 0<=x and x<len(graph)
        y_range = 0<=y and y<len(graph[0])
        return x_range and y_range
        
    #function to perform the depth-first search
    #on every unvisited node
    
    def dfs(self, node, graph):
        
        #mark the particular node to be visited
        self.visited_nodes[node[0]][node[1]] = True
        
        movements = [[-1, 0], [1, 0], [0, 1], [0, -1],
                    [1, 1], [1, -1], [-1, 1], [-1, -1]]
        for m in movements:
            i = node[0] + m[0]
            j = node[1] + m[1]
            
            #performing the depth-first search on nodes that are not visited yet 
            #and the cell is in range
            
            valid = self.valid_node(i,j,graph)
            if valid and graph[i][j]==1 and not self.visited_nodes[i][j]:
                self.dfs([i, j], graph)
                
    #function to return the number of islands 
    #found in the given 2D boolean matrix
    
    def number_of_Islands(self,graph):
        ones = []
        for i in range(len(graph)):
            self.visited_nodes.append([])
            for j in range(len(graph[i])):
                if graph[i][j] == 1:
                    ones.append([i, j])
                self.visited_nodes[i].append(False)
                
        #variable to count the number of islands        
        number_of_islands = 0
        
        for node in ones:
            if not self.visited_nodes[node[0]][node[1]]:
                self.dfs(node,graph)
                number_of_islands +=1
                
        return number_of_islands
 
graph =[[1, 1, 1, 0, 0],
        [0, 0, 0, 0, 1],
        [1, 0, 1, 1, 1],
        [0, 0, 0, 0, 0],
        [1, 0, 1, 0, 1]]

 
#making the object of Solution class        
obj=Solution()
answer = obj.number_of_Islands(graph)

 
#printing the answer
print("Total number of islands is"+" "+str(answer))


Output:

Total number of islands is 6


Explanation: Clearly, we can see the 6 islands in this graph.

Explanation

Complexity Analysis

Time Complexity: O(n*m), where n is the number of rows and m is the number of columns in an undirected graph's input boolean 2D matrix.

Reason: We are simply traversing the entire boolean matrix of size n*m and checking whether it is visited or not. So, traversing takes a complexity of O(n*m)

Auxiliary Space Complexity: O(n*m)

Reason: This algorithm required a matrix named visited of size n*m, which implies that this method occupies a space of n*m, making the space complexity as O(n*m)

Optimized Approach

The above method can further be optimized without using extra space, i.e., without using the visited matrix. Altogether the approach is almost the same as the earlier one. The only difference is we are changing the input 2D boolean matrix itself to mark a particular cell as visited (i.e., g[i][j]==-1) rather than using the extra space of equal size as the matrix and using that matrix to track the visited cells. We traverse the complete matrix and recursively perform Breadth-First Search on all 8 neighbors of a node and keep finding an island.

Algorithm

  • We traverse the given matrix for each row and column, and if the island is not visited, then we run a breadth-first search algorithm on all 8 neighbors.
     
  • We check for each neighbor separately if the neighbor is not visited, then enqueue the node in the queue and run a while loop to traverse the nodes in a BFS manner. 
     
  • Once all the neighbors are considered, and no new connected node is left. We remove the current node from the queue.

 

  • We count the number of times the BFS loop is called, giving us the required value, i.e., the number of islands. 
     
  • Return the number of islands to the main function and print the value.]

 

Let us understand the algorithm by performing a dry run on an example. 

Example input 

graph = [ [1, 1, 1, 0, 0],

               [0, 0, 0, 0, 1],

               [1, 0, 1, 1, 1],

               [0, 0, 0, 0, 0],

               [1, 0, 1, 0, 1] ]

We begin with index (0,0) and find an island (i.e., 1). So, we check for the neighbors of (0,0) and add those that have the value 1 to the queue(here (0,1)) and mark (0,0) as visited. 

Step 1

Now we check for the neighbors of (0,1) and add (0,2) to the queue. We ignore (0,0) because it is already visited.

Step 2

Next, when we check for (0,2) we find no unvisited neighbor nodes with value 1. The node (0,1) is ignored because it is already visited. 

Step 3

So we find our first island and increment the numOfIslands by 1. 

Step 4

Similarly, we continue until we find another node with value 1 and repeat the whole process until we reach the bottom right element of the graph. We conclude that we have 6 islands in total in our example. 

Final output

Hence, output 6.

C++ Implementation

#include <iostream>
using namespace std;

#include<vector>
#include<queue>

/* This function will count the number of islands */
int numberOfIslands(vector<vector<int>> & grid, int n, int m){
    
    /* Queue is used to keep track of the connected parts of the graph */
    queue<pair<int, int>> q;
    pair<int, int> p; 

    int x, y, numOfIslands= 0;
    
    /* For each row */
    for(int i =0; i<n; i++){
        
        /* For each column */
        for(int j=0; j<m; j++){
            
            /* If the value is 1 then it is an island that is not visited yet*/
            if(grid[i][j] == 1){
                
                /* Add the cell to the queue */
                q.push(make_pair(i,j));
                /* -1 indicates that the island is visited */
                grid[i][j] =-1;
                
                /* Loop until all nodes are visited */
                while(! q.empty()){
                    p = q.front(); 
                    
                    // x will contain the row value and y will contain the column value
                    x = p.first;
                    y = p.second;
                    
                    //up cell 
                    if(x-1 >= 0){
                        if(grid[x-1][y] == 1){
                            q.push(make_pair(x-1, y));
                            grid[x-1][y] == -1;
                        }
                    }
                    
                    //down cell 
                    if(x+1 <= n-1){
                        if(grid[x+1][y] == 1){
                            q.push(make_pair(x+1, y));
                            grid[x+1][y] = -1;
                        }
                    }
                    
                    //left cell 
                    if(y-1 >= 0){
                        if (grid[x][y-1] == 1){
                            q.push(make_pair(x, y-1));
                            grid[x][y-1] = -1;
                        }
                    }
                    
                    //right
                    if(y+1 <= m-1){
                        if (grid[x][y+1] == 1){
                            q.push(make_pair(x, y+1));
                            grid[x][y+1] = -1;
                        }
                    }
                    
                    //top right 
                    if(x-1 >= 0 && y+1 <= m-1){
                        if (grid[x-1][y+1] == 1){
                            q.push(make_pair(x-1, y+1));
                            grid[x-1][y+1] = -1;
                        }
                    }
                    
                    //top left 
                    if(x-1 >= 0 && y-1 >= 0){
                        if (grid[x-1][y-1] == 1){
                            q.push(make_pair(x-1, y-1));
                            grid[x-1][y-1] = -1;
                        }
                    }
                    
                    //bottom right
                    if(x+1 <= n-1 && y+1 <= m-1){
                        if (grid[x+1][y+1] == 1){
                            q.push(make_pair(x+1, y+1));
                            grid[x+1][y+1] = -1;
                        }
                    }
                    
                    //top left 
                    if(x+1 <= n-1 && y-1 >= 0){
                        if (grid[x+1][y-1] == 1){
                            q.push(make_pair(x+1, y-1));
                            grid[x+1][y-1] = -1;
                        }
                    }
                    
                    /* Remove the  current cell from the queue */
                    q.pop();
                }
                
                numOfIslands ++; 
            }
        }
    }
    
    return numOfIslands; 
}

/* Driver Function */
int main()
{
    vector<vector<int>> graph;
    
    graph = {{1, 1, 1, 0, 0},
        {0, 0, 0, 0, 1},
        {1, 0, 1, 1, 1},
        {0, 0, 0, 0, 0},
        {1, 0, 1, 0, 1}};
          
    cout<<"Total number of islands is "<<numberOfIslands(graph, graph.size(), graph[0].size());
    return 0;
}

Python Implementation

def numberOfIslands(grid, n, m):
    
    '''Queue is used to keep track of the connected parts of the graph'''
    q = []
    
    numOfIslands= 0
    
    '''For each row '''
    for i in range(n):
        
        '''For each column'''
        for j in range(m):
            
            '''If the value is 1 then it is an island that is not visited yet'''
            if grid[i][j] == 1:
                
                '''Add the cell to the queue '''
                q.append([i,j])
                
                '''-1 indicates that the island is visited'''
                grid[i][j] = -1
                
                '''Loop until all nodes are visited'''
                while(len(q) != 0):
                    
                    p = q[0]
                    
                    '''x will contain the row value and y will contain the column value'''
                    x = p[0]
                    y = p[1]
                    
                    '''up cell'''
                    if x-1 >= 0:
                        if grid[x-1][y] == 1: 
                            q.append([x-1, y])
                            grid[x-1][y] == -1
                    
                    '''down cell'''
                    if x+1 <= n-1:
                        if grid[x+1][y] == 1:
                            q.append([x+1, y])
                            grid[x+1][y] = -1
                    
                    '''left cell'''
                    if y-1 >= 0:
                        if grid[x][y-1] == 1:
                            q.append([x, y-1])
                            grid[x][y-1] = -1
                    
                    '''right'''
                    if y+1 <= m-1:
                        if grid[x][y+1] == 1:
                            q.append([x, y+1])
                            grid[x][y+1] = -1
                    
                    '''top right'''
                    if x-1 >= 0 and y+1 <= m-1:
                        if grid[x-1][y+1] == 1:
                            q.append([x-1, y+1])
                            grid[x-1][y+1] = -1
                    
                    '''top left'''
                    if x-1 >= 0 and y-1 >= 0:
                        if grid[x-1][y-1] == 1:
                            q.append([x-1, y-1])
                            grid[x-1][y-1] = -1
                    
                    '''bottom right'''
                    if x+1 <= n-1 and y+1 <= m-1:
                        if grid[x+1][y+1] == 1:
                            q.append([x+1, y+1])
                            grid[x+1][y+1] = -1
                    
                    '''top left'''
                    if x+1 <= n-1 and y-1 >= 0:
                        if grid[x+1][y-1] == 1:
                            q.append([x+1, y-1])
                            grid[x+1][y-1] = -1
                    
                    '''Remove the current cell from the queue '''
                    q.pop(0)
                
                numOfIslands += 1

    return numOfIslands
    
    
'''Driver Function '''
def main():
    
    graph = [[1, 1, 1, 0, 0],
             [0, 0, 0, 0, 1],
             [1, 0, 1, 1, 1],
             [0, 0, 0, 0, 0],
             [1, 0, 1, 0, 1]]

    print("Total number of islands is ", numberOfIslands(graph, len(graph), len(graph[0])))
         
    return 0

'''Executing Main'''
main()


Output: 

Total number of islands is 6

Complexity Analysis

Time Complexity: O(n*m), where n is the number of rows and m is the number of columns in the input boolean 2D matrix of an undirected graph.

Reason: This method also traversed the complete boolean matrix for counting the number of islands. So, time complexity remains the same as O(n*m)

Auxiliary Space Complexity: O(n*m) 

Reason: BFS uses a queue structure to store the order of traversal. Hence a maximum of  n*m space is required at a time for this purpose. We are not using a visited matrix, so that space is now saved. 

Frequently Asked Questions

What is meant by an undirected graph?

An undirected graph is a collection of connected objects (also known as vertices or nodes) where all edges are two-way.

How do you find the number of connected components on a graph?

Mark each vertex as unvisited to start. Repeat after each vertex. DFS should be used on any unvisited vertex to increase the count by one. The value of count will represent the number of connected elements in the graph following iteration over all vertices.

How does DFS work?

When a search runs into a dead end during any iteration, the Depth First Search (DFS) algorithm employs a stack to keep track of where to go next to continue the search.

How does BFS work?

BFS stands for Breadth-first search. It is a traversal algorithm for graphs where the traversal is done level by level. We traverse the nodes at the k level before moving to those at the k+1 level.  

What is a graph?

A graph is a non-linear data structure used to represent highly correlated data. It consists of vertices and edges. The vertices represent the nodes or elements of the graph, and the edges represent the relationships or connections between the nodes. 

Conclusion

This article discussed the problem of finding the number of islands. We have discussed the brute force solution where, we used DFS Algorithm and an additional visited matrix to solve the problem. We then discussed the optimized approach using BFS

We hope this blog helped you readily understand this problem and enhanced your knowledge about Depth-First Search and Breadth-First-Search used in Graphs

Recommended Readings:

Refer to our guided paths on Coding Ninjas Studio, a platform we provide, Coding Ninjas. You can upskill yourself in Data Structure AlgorithmsSystem DesignBasics of Machine Learning, and many more topics.

If you find our blogs informative and exciting, please vote for them.

Happy Coding and Learning!

Previous article
Find the number of islands
Next article
Count Cycles of Length n in an Undirected and Connected Graph
Live masterclass