Islas en un gráfico usando BFS

Dada una array booleana 2D, encuentre el número de islas. Un grupo de unos conectados forma una isla. Por ejemplo, la siguiente array contiene 5 islas

Ejemplo:  

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

¿Qué es una isla?  
Un grupo de unos conectados forma una isla. Por ejemplo, la siguiente array contiene 5 islas 

                        {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}

Esta es una variación del problema estándar: componente conectado . Un componente conexo de un grafo no dirigido es un subgrafo en el que cada dos vértices están conectados entre sí por un camino o caminos, y que no está conectado a ningún otro vértice fuera del subgrafo. 

Por ejemplo, el gráfico que se muestra a continuación tiene tres componentes conectados. 
 

Un gráfico donde todos los vértices están conectados entre sí tiene exactamente un componente conectado, que consiste en todo el gráfico. Tal gráfico con solo un componente conectado se llama Gráfico fuertemente conectado.
Hemos discutido una solución DFS para islas que ya se ha discutido. Este problema también se puede resolver aplicando BFS() en cada componente. En cada llamada BFS(), se visita un componente o un subgráfico. Llamaremos a BFS en el siguiente componente no visitado. El número de llamadas a BFS() da el número de componentes conectados. También se puede utilizar BFS.

Una celda en array 2D se puede conectar a 8 vecinos. Entonces, a diferencia de BFS() estándar, donde procesamos todos los vértices adyacentes, procesamos solo 8 vecinos. Realizamos un seguimiento de los 1 visitados para que no se vuelvan a visitar. 

C++

// A BFS based solution to count number of
// islands in a graph.
#include <bits/stdc++.h>
using namespace std;
 
// R x C matrix
#define R 5
#define C 5
 
// A function to check if a given cell
// (u, v) can be included in DFS
bool isSafe(int mat[R][C], int i, int j,
            bool vis[R][C])
{
    return (i >= 0) && (i < R) &&
           (j >= 0) && (j < C) &&
           (mat[i][j] && !vis[i][j]);
}
 
void BFS(int mat[R][C], bool vis[R][C],
         int si, int sj)
{
 
    // These arrays are used to get row and
    // column numbers of 8 neighbours of
    // a given cell
    int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
    // Simple BFS first step, we enqueue
    // source and mark it as visited
    queue<pair<int, int> > q;
    q.push(make_pair(si, sj));
    vis[si][sj] = true;
 
    // Next step of BFS. We take out
    // items one by one from queue and
    // enqueue their univisited adjacent
    while (!q.empty()) {
 
        int i = q.front().first;
        int j = q.front().second;
        q.pop();
 
        // Go through all 8 adjacent
        for (int k = 0; k < 8; k++) {
            if (isSafe(mat, i + row[k],
                       j + col[k], vis)) {
             vis[i + row[k]][j + col[k]] = true;
             q.push(make_pair(i + row[k], j + col[k]));
            }
        }
    }
}
 
// This function returns number islands (connected
// components) in a graph. It simply works as
// BFS for disconnected graph and returns count
// of BFS calls.
int countIslands(int mat[R][C])
{
    // Mark all cells as not visited
    bool vis[R][C];
    memset(vis, 0, sizeof(vis));
 
    // Call BFS for every unvisited vertex
    // Whenever we see an univisted vertex,
    // we increment res (number of islands)
    // also.
    int res = 0;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            if (mat[i][j] && !vis[i][j]) {
                BFS(mat, vis, i, j);
                res++;
            }
        }
    }
 
    return res;
}
 
// main function
int main()
{
    int mat[][C] = { { 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 << countIslands(mat);
 
    return 0;
}

Java

// A BFS based solution to count number of
// islands in a graph.
import java.util.*;
 
class GFG
{
 
// R x C matrix
static final int R = 5;
static final int C = 5 ;
static class pair
{
    int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// A function to check if a given cell
// (u, v) can be included in DFS
static boolean isSafe(int mat[][], int i, int j,
                       boolean vis[][])
{
    return (i >= 0) && (i < R) &&
        (j >= 0) && (j < C) &&
        (mat[i][j]==1 && !vis[i][j]);
}
 
static void BFS(int mat[][], boolean vis[][],
                int si, int sj)
{
 
    // These arrays are used to get row and
    // column numbers of 8 neighbours of
    // a given cell
    int row[] = { -1, -1, -1, 0, 0, 1, 1, 1 };
    int col[] = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
    // Simple BFS first step, we enqueue
    // source and mark it as visited
    Queue<pair> q = new LinkedList<pair>();
    q.add(new pair(si, sj));
    vis[si][sj] = true;
 
    // Next step of BFS. We take out
    // items one by one from queue and
    // enqueue their univisited adjacent
    while (!q.isEmpty())
    {
 
        int i = q.peek().first;
        int j = q.peek().second;
        q.remove();
 
        // Go through all 8 adjacent
        for (int k = 0; k < 8; k++)
        {
            if (isSafe(mat, i + row[k],
                    j + col[k], vis))
            {
                vis[i + row[k]][j + col[k]] = true;
                q.add(new pair(i + row[k], j + col[k]));
            }
        }
    }
}
 
// This function returns number islands (connected
// components) in a graph. It simply works as
// BFS for disconnected graph and returns count
// of BFS calls.
static int countIslands(int mat[][])
{
    // Mark all cells as not visited
    boolean [][]vis = new boolean[R][C];
 
    // Call BFS for every unvisited vertex
    // Whenever we see an univisted vertex,
    // we increment res (number of islands)
    // also.
    int res = 0;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (mat[i][j]==1 && !vis[i][j])
            {
                BFS(mat, vis, i, j);
                res++;
            }
        }
    }
    return res;
}
 
// Driver code
public static void main(String[] args)
{
    int 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 } };
 
    System.out.print(countIslands(mat));
}
}
 
// This code is contributed by PrinciRaj1992

Python3

# A BFS based solution to count number of
# islands in a graph.
from collections import deque
 
# A function to check if a given cell
# (u, v) can be included in DFS
def isSafe(mat, i, j, vis):
     
    return ((i >= 0) and (i < 5) and 
            (j >= 0) and (j < 5) and
          (mat[i][j] and (not vis[i][j])))
 
def BFS(mat, vis, si, sj):
     
    # These arrays are used to get row and
    # column numbers of 8 neighbours of
    # a given cell
    row = [-1, -1, -1, 0, 0, 1, 1, 1]
    col = [-1, 0, 1, -1, 1, -1, 0, 1]
 
    # Simple BFS first step, we enqueue
    # source and mark it as visited
    q = deque()
    q.append([si, sj])
    vis[si][sj] = True
 
    # Next step of BFS. We take out
    # items one by one from queue and
    # enqueue their univisited adjacent
    while (len(q) > 0):
        temp = q.popleft()
 
        i = temp[0]
        j = temp[1]
 
        # Go through all 8 adjacent
        for k in range(8):
            if (isSafe(mat, i + row[k], j + col[k], vis)):
                vis[i + row[k]][j + col[k]] = True
                q.append([i + row[k], j + col[k]])
 
# This function returns number islands (connected
# components) in a graph. It simply works as
# BFS for disconnected graph and returns count
# of BFS calls.
def countIslands(mat):
      
    # Mark all cells as not visited
    vis = [[False for i in range(5)]
                  for i in range(5)]
    # memset(vis, 0, sizeof(vis));
 
    # 5all BFS for every unvisited vertex
    # Whenever we see an univisted vertex,
    # we increment res (number of islands)
    # also.
    res = 0
 
    for i in range(5):
        for j in range(5):
            if (mat[i][j] and not vis[i][j]):
                BFS(mat, vis, i, j)
                res += 1
 
    return res
 
# Driver code
if __name__ == '__main__':
     
    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 ]]
 
    print (countIslands(mat))
 
# This code is contributed by mohit kumar 29

C#

// A BFS based solution to count number of
// islands in a graph.
using System;
using System.Collections.Generic;
 
class GFG
{
 
// R x C matrix
static readonly int R = 5;
static readonly int C = 5 ;
class pair
{
    public int first, second;
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
// A function to check if a given cell
// (u, v) can be included in DFS
static bool isSafe(int [,]mat, int i, int j,
                    bool [,]vis)
{
    return (i >= 0) && (i < R) &&
        (j >= 0) && (j < C) &&
        (mat[i, j]==1 && !vis[i, j]);
}
 
static void BFS(int [,]mat, bool [,]vis,
                int si, int sj)
{
 
    // These arrays are used to get row and
    // column numbers of 8 neighbours of
    // a given cell
    int []row = { -1, -1, -1, 0, 0, 1, 1, 1 };
    int []col = { -1, 0, 1, -1, 1, -1, 0, 1 };
 
    // Simple BFS first step, we enqueue
    // source and mark it as visited
    List<pair> q = new List<pair>();
    q.Add(new pair(si, sj));
    vis[si, sj] = true;
 
    // Next step of BFS. We take out
    // items one by one from queue and
    // enqueue their univisited adjacent
    while (q.Count != 0)
    {
        int i = q[0].first;
        int j = q[0].second;
        q.RemoveAt(0);
 
        // Go through all 8 adjacent
        for (int k = 0; k < 8; k++)
        {
            if (isSafe(mat, i + row[k],
                    j + col[k], vis))
            {
                vis[i + row[k], j + col[k]] = true;
                q.Add(new pair(i + row[k], j + col[k]));
            }
        }
    }
}
 
// This function returns number islands (connected
// components) in a graph. It simply works as
// BFS for disconnected graph and returns count
// of BFS calls.
static int countIslands(int [,]mat)
{
    // Mark all cells as not visited
    bool [,]vis = new bool[R, C];
 
    // Call BFS for every unvisited vertex
    // Whenever we see an univisted vertex,
    // we increment res (number of islands)
    // also.
    int res = 0;
    for (int i = 0; i < R; i++)
    {
        for (int j = 0; j < C; j++)
        {
            if (mat[i, j]==1 && !vis[i, j])
            {
                BFS(mat, vis, i, j);
                res++;
            }
        }
    }
    return res;
}
 
// Driver code
public static void Main(String[] args)
{
    int [,]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 } };
 
    Console.Write(countIslands(mat));
}
}
 
// This code is contributed by 29AjayKumar

Javascript

<script>
// A BFS based solution to count number of
// islands in a graph.
 
// R x C matrix
let R = 5;
let C = 5 ;
 
// A function to check if a given cell
// (u, v) can be included in DFS
function isSafe(mat,i,j,vis)
{
    return (i >= 0) && (i < R) &&
        (j >= 0) && (j < C) &&
        (mat[i][j] == 1 && !vis[i][j]);
}
 
function BFS(mat, vis, si, sj)
{
 
    // These arrays are used to get row and
    // column numbers of 8 neighbours of
    // a given cell
       let row = [ -1, -1, -1, 0, 0, 1, 1, 1 ];
    let col = [ -1, 0, 1, -1, 1, -1, 0, 1 ];
  
    // Simple BFS first step, we enqueue
    // source and mark it as visited
    let q = [];
    q.push([si, sj]);
    vis[si][sj] = true;
  
    // Next step of BFS. We take out
    // items one by one from queue and
    // enqueue their univisited adjacent
    while (q.length != 0)
    {
  
        let i = q[0][0];
        let j = q[0][1];
        q.shift();
  
        // Go through all 8 adjacent
        for (let k = 0; k < 8; k++)
        {
            if (isSafe(mat, i + row[k],
                    j + col[k], vis))
            {
                vis[i + row[k]][j + col[k]] = true;
                q.push([i + row[k], j + col[k]]);
            }
        }
    }
}
 
// This function returns number islands (connected
// components) in a graph. It simply works as
// BFS for disconnected graph and returns count
// of BFS calls.
function countIslands(mat)
{
 
    // Mark all cells as not visited
    let vis = new Array(R);
    for(let i = 0; i < R; i++)
    {
        vis[i] = new Array(C);
        for(let j = 0; j < C; j++)
        {
            vis[i][j] = false;
        }
    }
  
    // Call BFS for every unvisited vertex
    // Whenever we see an univisted vertex,
    // we increment res (number of islands)
    // also.
    let res = 0;
    for (let i = 0; i < R; i++)
    {
        for (let j = 0; j < C; j++)
        {
            if (mat[i][j] == 1 && !vis[i][j])
            {
                BFS(mat, vis, i, j);
                res++;
            }
        }
    }
    return res;
}
 
// Driver code
let 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 ] ];
                     
document.write(countIslands(mat));
 
// This code is contributed by patel2127.
</script>
Producción: 

5

 

Complejidad de tiempo: O (ROW * COL) donde ROW es el número de FILAS y COL es el número de COLUMNAS en la array. 

Publicación traducida automáticamente

Artículo escrito por kartik y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *