Рубрики

Найти количество островов | Набор 1 (с использованием DFS)

Учитывая булеву 2D матрицу, найдите количество островков. Группа связанных 1s образует остров. Например, приведенная ниже матрица содержит 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

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

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

Граф, в котором все вершины связаны друг с другом, имеет ровно одну связную компоненту, состоящую из всего графа. Такой граф только с одним связным компонентом называется сильно связным графом.

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

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

Ячейка в 2D-матрице может быть связана с 8 соседями. Таким образом, в отличие от стандартного DFS (), где мы рекурсивно вызываем все смежные вершины, здесь мы можем рекурсивно вызывать только 8 соседей. Мы отслеживаем посещенные 1, чтобы они больше не посещались.

C ++

// C ++ Программа для подсчета островов в булевой 2D матрице
#include <bits/stdc++.h>

using namespace std;

  
#define ROW 5
#define COL 5

  
// Функция для проверки, если данный
// ячейка (строка, столбец) может быть включена в DFS

int isSafe(int M[][COL], int row, int col,

           bool visited[][COL])

{

    // номер строки в диапазоне, столбец

    // число находится в диапазоне и значение равно 1

    // и еще не посещал

    return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]);

}

  
// Вспомогательная функция для создания DFS для
// 2D булева матрица. Это только считает
// 8 соседей как смежные вершины

void DFS(int M[][COL], int row, int col,

         bool visited[][COL])

{

    // Эти массивы используются для получения

    // номера строк и столбцов 8

    // соседи данной ячейки

    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

  

    // Пометить эту ячейку как посещенную

    visited[row][col] = true;

  

    // повторить для всех подключенных соседей

    for (int k = 0; k < 8; ++k)

        if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))

            DFS(M, row + rowNbr[k], col + colNbr[k], visited);

}

  
// Основная функция, которая возвращает
// количество островов в данном логическом значении
// 2D матрица

int countIslands(int M[][COL])

{

    // Создать массив bool для отметки посещенных ячеек.

    // изначально все ячейки не посещены

    bool visited[ROW][COL];

    memset(visited, 0, sizeof(visited));

  

    // Инициализируем count как 0 и

    // пройти через все клетки

    // заданная матрица

    int count = 0;

    for (int i = 0; i < ROW; ++i)

        for (int j = 0; j < COL; ++j)

  

            // Если ячейка со значением 1 не

            if (M[i][j] && !visited[i][j]) {

                // посетили еще, потом наш новый остров

                // Посетить все клетки на этом острове.

                DFS(M, i, j, visited);

  

                // и увеличиваем количество островов

                ++count;

            }

  

    return count;

}

  
// Код драйвера

int main()

{

    int M[][COL] = { { 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 } };

  

    cout << "Number of islands is: " << countIslands(M);

  

    return 0;

}

  
// Это код, предоставленный rathbhupendra

С

// Программа для подсчета островов в булевой 2D матрице
#include <stdbool.h>
#include <stdio.h>
#include <string.h>

  
#define ROW 5
#define COL 5

  
// Функция для проверки, может ли данная ячейка (строка, столбец) быть включена в DFS

int isSafe(int M[][COL], int row, int col, bool visited[][COL])

{

    // номер строки в диапазоне, номер столбца в диапазоне и значение 1

    // и еще не посещал

    return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] && !visited[row][col]);

}

  
// Вспомогательная функция для создания DFS для двумерной логической матрицы. Это только считает
// 8 соседей как смежные вершины

void DFS(int M[][COL], int row, int col, bool visited[][COL])

{

    // Эти массивы используются для получения номеров строк и столбцов 8 соседей

    // данной ячейки

    static int rowNbr[] = { -1, -1, -1, 0, 0, 1, 1, 1 };

    static int colNbr[] = { -1, 0, 1, -1, 1, -1, 0, 1 };

  

    // Пометить эту ячейку как посещенную

    visited[row][col] = true;

  

    // повторить для всех подключенных соседей

    for (int k = 0; k < 8; ++k)

        if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))

            DFS(M, row + rowNbr[k], col + colNbr[k], visited);

}

  
// Основная функция, которая возвращает количество островов в данном логическом значении
// 2D матрица

int countIslands(int M[][COL])

{

    // Создать массив bool для отметки посещенных ячеек.

    // изначально все ячейки не посещены

    bool visited[ROW][COL];

    memset(visited, 0, sizeof(visited));

  

    // Инициализировать count как 0 и пройти через все ячейки

    // заданная матрица

    int count = 0;

    for (int i = 0; i < ROW; ++i)

        for (int j = 0; j < COL; ++j)

            if (M[i][j] && !visited[i][j]) // Если ячейка со значением 1 не

            { // посетили еще, потом наш новый остров

                DFS(M, i, j, visited); // Посетить все клетки на этом острове.

                ++count; // и увеличиваем количество островов

            }

  

    return count;

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    int M[][COL] = { { 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 } };

  

    printf("Number of islands is: %d\n", countIslands(M));

  

    return 0;

}

Джава

// Java-программа для подсчета островов в булевой 2D-матрице

import java.util.*;

import java.lang.*;

import java.io.*;

  

class Islands {

    // Нет строк и столбцов

    static final int ROW = 5, COL = 5;

  

    // Функция для проверки, может ли данная ячейка (строка, столбец)

    // быть включенным в DFS

    boolean isSafe(int M[][], int row, int col,

                   boolean visited[][])

    {

        // номер строки находится в диапазоне, номер столбца находится в диапазоне

        // а значение равно 1 и еще не посещено

        return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row][col] == 1 && !visited[row][col]);

    }

  

    // Вспомогательная функция для создания DFS для двумерной логической матрицы.

    // Он рассматривает только 8 соседей как смежные вершины

    void DFS(int M[][], int row, int col, boolean visited[][])

    {

        // Эти массивы используются для получения номеров строк и столбцов

        // из 8 соседей данной ячейки

        int rowNbr[] = new int[] { -1, -1, -1, 0, 0, 1, 1, 1 };

        int colNbr[] = new int[] { -1, 0, 1, -1, 1, -1, 0, 1 };

  

        // Пометить эту ячейку как посещенную

        visited[row][col] = true;

  

        // повторить для всех подключенных соседей

        for (int k = 0; k < 8; ++k)

            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))

                DFS(M, row + rowNbr[k], col + colNbr[k], visited);

    }

  

    // Основная функция, которая возвращает количество островов в данном

    // логическая 2D матрица

    int countIslands(int M[][])

    {

        // Создать массив bool для отметки посещенных ячеек.

        // изначально все ячейки не посещены

        boolean visited[][] = new boolean[ROW][COL];

  

        // Инициализировать count как 0 и пройти через все ячейки

        // данной матрицы

        int count = 0;

        for (int i = 0; i < ROW; ++i)

            for (int j = 0; j < COL; ++j)

                if (M[i][j] == 1 && !visited[i][j]) // Если ячейка с

                { // значение 1 не

                    // посетили еще, потом наш новый остров, Посетить все

                    // ячейки на этом острове и увеличение количества островов

                    DFS(M, i, j, visited);

                    ++count;

                }

  

        return count;

    }

  

    // Метод драйвера

    public static void main(String[] args) throws java.lang.Exception

    {

        int M[][] = new int[][] { { 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 } };

        Islands I = new Islands();

        System.out.println("Number of islands is: " + I.countIslands(M));

    }

} // Аакаш Хасия

питон

# Программа для подсчета островов в булевой 2D матрице

class Graph:

  

    def __init__(self, row, col, g):

        self.ROW = row

        self.COL = col

        self.graph = g

  

    # Функция для проверки, если данная ячейка

    # (строка, столбец) может быть включен в DFS

    def isSafe(self, i, j, visited):

        # номер строки находится в диапазоне, номер столбца

        # находится в диапазоне и значение 1

        # и еще не посещал

        return (i >= 0 and i < self.ROW and 

                j >= 0 and j < self.COL and 

                not visited[i][j] and self.graph[i][j])

              

  

    # Полезная функция для создания DFS для 2D

    # булева матрица. Это только считает

    # 8 соседей как смежные вершины

    def DFS(self, i, j, visited):

  

        # Эти массивы используются для получения строки и

        # номера столбцов 8 соседей

        # данной ячейки

        rowNbr = [-1, -1, -10, 01, 1, 1];

            colNbr = [-101, -1, 1, -1, 0, 1];

          

        # Отметить эту ячейку как посещенную

        visited[i][j] = True

  

        # Повторить для всех подключенных соседей

        for k in range(8):

            if self.isSafe(i + rowNbr[k], j + colNbr[k], visited):

                self.DFS(i + rowNbr[k], j + colNbr[k], visited)

  

  

    # Основная функция, которая возвращает

    # количество островов в данном логическом значении

    # 2D матрица

    def countIslands(self):

        # Создайте массив bool для отметки посещенных ячеек.

        # Первоначально все ячейки не посещены

        visited = [[False for j in range(self.COL)]for i in range(self.ROW)]

  

        # Инициализировать считать как 0 и путешествовать

        # через все клетки

        # заданная матрица

        count = 0

        for i in range(self.ROW):

            for j in range(self.COL):

                # Если ячейка со значением 1 еще не посещена,

                # тогда новый остров найден

                if visited[i][j] == False and self.graph[i][j] == 1:

                    # Посетите все клетки на этом острове

                    # и увеличение числа островов

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

  
# Этот код предоставлен Neelam Yadav

C #

// C # программа для подсчета
// острова в логическом
// 2D матрица

using System;

  

class GFG {

    // Нет строк

    // и столбцы

    static int ROW = 5, COL = 5;

  

    // Функция для проверки

    // данная ячейка (строка, столбец)

    // может быть включен в DFS

    static bool isSafe(int[, ] M, int row,

                       int col, bool[, ] visited)

    {

        // номер строки находится в диапазоне,

        // номер столбца находится в диапазоне

        // и значение равно 1, а не

        // еще посетил

        return (row >= 0) && (row < ROW) && (col >= 0) && (col < COL) && (M[row, col] == 1 && !visited[row, col]);

    }

  

    // Полезная функция для выполнения

    // DFS для двумерной булевой матрицы.

    // Он учитывает только 8

    // соседи как смежные вершины

    static void DFS(int[, ] M, int row,

                    int col, bool[, ] visited)

    {

        // Эти массивы используются для

        // получаем номера строк и столбцов

        // из 8 соседей данной ячейки

        int[] rowNbr = new int[] { -1, -1, -1, 0,

                                   0, 1, 1, 1 };

        int[] colNbr = new int[] { -1, 0, 1, -1,

                                   1, -1, 0, 1 };

  

        // Отметить эту ячейку

        // как посетил

        visited[row, col] = true;

  

        // повторить для всех

        // подключенные соседи

        for (int k = 0; k < 8; ++k)

            if (isSafe(M, row + rowNbr[k], col + colNbr[k], visited))

                DFS(M, row + rowNbr[k],

                    col + colNbr[k], visited);

    }

  

    // Основная функция, которая

    // возвращает количество островов

    // в заданной булевой 2D матрице

    static int countIslands(int[, ] M)

    {

        // Сделать массив bool для

        // пометить посещенные ячейки.

        // Изначально все ячейки

        // не посещаем

        bool[, ] visited = new bool[ROW, COL];

  

        // Инициализируем count как 0 и

        // путешествовать по всему

        // ячейки данной матрицы

        int count = 0;

        for (int i = 0; i < ROW; ++i)

            for (int j = 0; j < COL; ++j)

                if (M[i, j] == 1 && !visited[i, j]) {

                    // Если ячейка со значением 1 не

                    // посетили еще, потом новый остров

                    // найдено, Посетите все ячейки в этом

                    // остров и увеличение количества островов

                    DFS(M, i, j, visited);

                    ++count;

                }

  

        return count;

    }

  

    // Код драйвера

    public static void Main()

    {

        int[, ] M = new int[, ] { { 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 } };

        Console.Write("Number of islands is: " + countIslands(M));

    }

}

  
// Этот код добавлен
// от shiv_bhakt.

PHP

<?php 
// Программа для подсчета островов
// в булевой 2D матрице

  

$ROW = 5;

$COL = 5;

  
// Функция для проверки, если
// данная ячейка (строка, столбец) может
// быть включенным в DFS

function isSafe(&$M, $row, $col,

                &$visited)

{

    global $ROW, $COL;

      

    // номер строки находится в диапазоне,

    // номер столбца в

    // диапазон и значение 1

    // и еще не посещал

    return ($row >= 0) && ($row < $ROW) &&     

           ($col >= 0) && ($col < $COL) &&     

           ($M[$row][$col] && 

             !isset($visited[$row][$col])); 

}

  
// Утилита для работы с DFS
// для двумерной булевой матрицы. Это
// учитывает только 8 соседей
// как смежные вершины

function DFS(&$M, $row, $col,

            &$visited)

{

    // Эти массивы используются для

    // получаем номера строк и столбцов

    // из 8 соседей данной ячейки

    $rowNbr = array(-1, -1, -1, 0, 

                    0, 1, 1, 1);

    $colNbr = array(-1, 0, 1, -1, 

                    1, -1, 0, 1);

  

    // Пометить эту ячейку как посещенную

    $visited[$row][$col] = true;

  

    // повторить для всех

    // подключенные соседи

    for ($k = 0; $k < 8; ++$k)

        if (isSafe($M, $row + $rowNbr[$k], 

                $col + $colNbr[$k], $visited))

            DFS($M, $row + $rowNbr[$k], 

                $col + $colNbr[$k], $visited);

}

  
// Основная функция, которая возвращает
// количество островов в данном
// логическая 2D матрица

function countIslands(&$M)

{

    global $ROW, $COL;

      

    // Сделать массив bool для

    // пометить посещенные ячейки.

    // Изначально все ячейки

    // не посещаем

    $visited = array(array());

  

    // Инициализируем count как 0 и

    // путешествовать по всему

    // ячейки данной матрицы

    $count = 0;

    for ($i = 0; $i < $ROW; ++$i)

        for ($j = 0; $j < $COL; ++$j)

            if ($M[$i][$j] && 

                 !isset($visited[$i][$j])) // Если ячейка со значением 1

            {                               // еще не посещен,

                DFS($M, $i, $j, $visited); // тогда найден новый остров

                ++$count;                   // Посетить все ячейки в этом

            }                               // остров и приращение

                                           // количество островов.

  

    return $count;

}

  
// Код драйвера

$M = array(array(1, 1, 0, 0, 0),

           array(0, 1, 0, 0, 1),

           array(1, 0, 0, 1, 1),

            array(0, 0, 0, 0, 0),

           array(1, 0, 1, 0, 1));

  

echo "Number of islands is: ",

            countIslands($M);

  
// Этот код добавлен
// ChitraNayal
?>

Выход:

Number of islands is: 5

Временная сложность: O (ROW x COL)

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

Ссылка:
http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Найти количество островов | Набор 1 (с использованием DFS)

0.00 (0%) 0 votes