Number of Islands

Hints

• https://www.geeksforgeeks.org/find-the-number-of-islands-using-dfs/
• Count the number ofconnected_components in aundirected_graph

Intuition

• An element in a Matrix can have maximum 8 neighbours.
• initialization_phase has count variable.
• There are two nested loops for row x column, this time complexity r*c
• In themaintaince_phase if element at i, j location is 1 then call DFS method and increase the count by 1
• It is a modified version of DFS with Recursion, calling DFS 8 times inside, what is this type of recursion called?
• What is thebaseCondition
• Why in below code row and col have been assigned? Graph can be stored asadjacency_matrix as well so that is done here.
• Why is graph 0th row selected for column?
• Why is the base condition so complex?
  • Base says if i is greater than 0, what is i? i is row and j is column
  • Why should i be greater than graph length
  • Why should j be greater than graph[0] length?
  • Why should it break therecursion if graph(i)(j) is not 1?
• In countIslands method why has the count variable defined and initiated? Can’t it be moved to DFS method?
• Why are some elements get marked as -1, what places will this affect in countIslands method or dfs method?
  • In dfs method base condition

Code

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())
 

Code in Javascript

class Graph {
    constructor(row, col, graph) {
        this.ROW = row;
        this.COL = col;
        this.graph = graph;
    }
 
    // A utility function to do DFS for a 2D
    // boolean matrix. It only considers
    // the 8 neighbours as adjacent vertices
    DFS(i, j) {
        if (i < 0 || i >= this.graph.length || j < 0 || j >= this.graph[0].length || this.graph[i][j] !== 1) {
            return;
        }
 
        // mark it as visited
        this.graph[i][j] = -1;
 
        // Recur for 8 neighbours
        this.DFS(i - 1, j - 1);
        this.DFS(i - 1, j);
        this.DFS(i - 1, j + 1);
        this.DFS(i, j - 1);
        this.DFS(i, j + 1);
        this.DFS(i + 1, j - 1);
        this.DFS(i + 1, j);
        this.DFS(i + 1, j + 1);
    }
 
    // The main function that returns
    // count of islands in a given boolean
    // 2D matrix
    countIslands() {
        // Initialize count as 0 and traverse
        // through the all cells of
        // given matrix
        let count = 0;
        for (let i = 0; i < this.ROW; i++) {
            for (let j = 0; j < this.COL; j++) {
                // If a cell with value 1 is not visited yet,
                // then new island found
                if (this.graph[i][j] === 1) {
                    // Visit all cells in this island
                    // and increment island count
                    this.DFS(i, j);
                    count++;
                }
            }
        }
        return count;
    }
}
 
let graph = [
    [1, 1, 0, 0, 0],
    [0, 1, 0, 0, 1],
    [1, 0, 0, 1, 1],
    [0, 0, 0, 0, 0],
    [