Найдите количество островов с помощью DFS

Учитывая бинарную двумерную матрицу, найдите количество островов. Группа соединенных единиц образует остров. Например, приведенная ниже матрица содержит 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, 0}}
Output: 5

Это вариация стандартной задачи: «Подсчет количества компонент связности в неориентированном графе».

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

Граф, все вершины которого связаны друг с другом, имеет ровно одну компоненту связности, состоящую из всего графа. Такой граф, содержащий только одну связную компоненту, называется сильносвязным графом.
Эту проблему можно легко решить, применив DFS() к каждому компоненту. При каждом вызове DFS() посещается компонент или подграф. Мы будем вызывать DFS для следующего непосещенного компонента. Количество вызовов DFS() дает количество подключенных компонентов. Также можно использовать BFS.

Что такое остров?
Группа соединенных единиц образует остров. Например, приведенная ниже матрица содержит 4 острова.

Нахождение количества островов с помощью дополнительной матрицы:

The idea is to keep an additional matrix to keep track of the visited nodes in the given matrix, and perform DFS to find the total number of islands

Выполните следующие шаги, чтобы решить проблему:

• Инициализировать посещаемую логическую матрицу размера данной матрицы значением false .
• Инициализируйте count = 0 , чтобы сохранить ответ.
• Пройдите цикл от 0 до ROW
  • Пройти вложенный цикл от 0 до COL
    • Если значение текущей ячейки в данной матрице равно 1 и не посещается
      • Вызов функции DFS
        • Инициализировать rowNbr[] = {-1, -1, -1, 0, 0, 1, 1, 1} и colNbr[] = {-1, 0, 1, -1, 1, -1, 0, 1} для соседних ячеек.
        • Отметить текущую ячейку как посещенную
        • Запустите цикл от 0 до 8 , чтобы обойти соседа
          • Если сосед безопасен для посещения и не посещается
            • Рекурсивно вызывать DFS на соседнем устройстве.
      • Увеличение счетчика на 1
• Возврат считается окончательным ответом.

Ниже приведена реализация кода вышеуказанного подхода:

Временная сложность: O(ROW x COL), где ROW — количество строк, а COL — количество столбцов в данной матрице.
Вспомогательное пространство: O(ROW x COL) для создания дополнительной посещенной матрицы.

Нахождение количества островов с помощью DFS :

The idea is to modify the given matrix, and perform DFS to find the total number of islands

Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте count = 0 , чтобы сохранить ответ.
• Пройдите цикл от 0 до ROW
  • Пройти вложенный цикл от 0 до COL
    • Если значение текущей ячейки в данной матрице равно 1
      • Увеличение счетчика на 1
      • Вызов функции DFS
        • Если ячейка выходит за границу или значение в текущей ячейке равно 0
          • Возвращаться.
        • Обновите значение в текущей ячейке как 0 .
        • Рекурсивно вызывать DFS для соседа
• Возврат считается окончательным ответом.

Ниже приведена реализация кода вышеуказанного подхода:

Временная сложность: O(ROW x COL), где ROW — количество строк, а COL — количество столбцов в данной матрице.
Вспомогательное пространство: O(ROW * COL), так как для DFS нам нужно дополнительное вспомогательное пространство стека.

Найдите количество островов | Набор 2 (с использованием непересекающегося набора)
Острова на графике с использованием BFS