Программа Python для поиска количества островов | Набор 1 (с использованием DFS)

Опубликовано: 7 Октября, 2022

Учитывая логическую двумерную матрицу, найдите количество островов. Группа соединенных единиц образует остров. Например, приведенная ниже матрица содержит 5 островов.

Пример:

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

Это вариация стандартной задачи: «Подсчет количества компонент связности в неориентированном графе».
Прежде чем мы перейдем к проблеме, давайте разберемся, что такое связный компонент. Компонента связности неориентированного графа — это подграф, в котором каждые две вершины соединены друг с другом путем (путями) и который не связан ни с какими другими вершинами вне подграфа.
Например, граф, показанный ниже, имеет три компоненты связности.


Python




# 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
Пожалуйста, обратитесь к полной статье «Найти количество островов» | Установите 1 (используя DFS) для более подробной информации!

            

                            

                    
                                    

                        

                
РЕКОМЕНДУЕМЫЕ СТАТЬИ