Breadth First Traversal ( BFS ) en una array 2D

Dada una array de tamaño M x N que consiste en números enteros, la tarea es imprimir los elementos de la array utilizando el recorrido de búsqueda primero en amplitud .

Ejemplos:

Entrada: grid[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}
Salida : 1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16

Entrada: cuadrícula[][] = {{-1, 0, 0, 1}, {-1, -1, -2, -1}, {-1, -1, -1, -1}, {0 , 0, 0, 0}}
Salida: -1 0 -1 0 -1 -1 1 -2 -1 0 -1 -1 0 -1 0 0

Enfoque: siga los pasos a continuación para resolver el problema:

1. Inicialice los vectores de dirección dRow[] = {-1, 0, 1, 0} y dCol[] = {0, 1, 0, -1} y una cola de pares para almacenar los índices de las celdas de array.
2. Inicie el recorrido de BFS desde la primera celda, es decir, (0, 0) , y ponga en cola el índice de esta celda en la cola .
3. Inicialice una array booleana para marcar las celdas visitadas de la array. Marque la celda (0, 0) como visitada.
4. Declare una función isValid() para verificar si las coordenadas de la celda son válidas o no, es decir, se encuentran dentro de los límites de la Array dada y no se visitan o no.
5. Iterar mientras la cola no está vacía y realizar las siguientes operaciones:
   • Retire la celda presente al frente de la cola e imprímala.
   • Mover a sus celdas adyacentes que no son visitadas.
   • Márquelos como visitados y colóquelos en la cola.

Nota: Los vectores de dirección se utilizan para atravesar las celdas adyacentes de una celda determinada en un orden determinado. Por ejemplo (x, y) es una celda cuyas celdas adyacentes (x – 1, y), (x, y + 1), (x + 1, y), (x, y – 1) necesitan ser atravesadas, entonces se puede hacer usando los vectores de dirección (-1, 0), (0, 1), (1, 0), (0, -1) en el orden arriba, izquierda, abajo y derecha.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define ROW 4
#define COL 4
 
// Direction vectors
int dRow[] = { -1, 0, 1, 0 };
int dCol[] = { 0, 1, 0, -1 };
 
// Function to check if a cell
// is be visited or not
bool isValid(bool vis[][COL],
             int row, int col)
{
    // If cell lies out of bounds
    if (row < 0 || col < 0
        || row >= ROW || col >= COL)
        return false;
 
    // If cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise
    return true;
}
 
// Function to perform the BFS traversal
void BFS(int grid[][COL], bool vis[][COL],
         int row, int col)
{
    // Stores indices of the matrix cells
    queue<pair<int, int> > q;
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.push({ row, col });
    vis[row][col] = true;
 
    // Iterate while the queue
    // is not empty
    while (!q.empty()) {
 
        pair<int, int> cell = q.front();
        int x = cell.first;
        int y = cell.second;
 
        cout << grid[x][y] << " ";
 
        q.pop();
 
        // Go to the adjacent cells
        for (int i = 0; i < 4; i++) {
 
            int adjx = x + dRow[i];
            int adjy = y + dCol[i];
 
            if (isValid(vis, adjx, adjy)) {
                q.push({ adjx, adjy });
                vis[adjx][adjy] = true;
            }
        }
    }
}
 
// Driver Code
int main()
{
    // Given input matrix
    int grid[ROW][COL] = { { 1, 2, 3, 4 },
                           { 5, 6, 7, 8 },
                           { 9, 10, 11, 12 },
                           { 13, 14, 15, 16 } };
 
    // Declare the visited array
    bool vis[ROW][COL];
    memset(vis, false, sizeof vis);
 
    BFS(grid, vis, 0, 0);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static class pair
{
    int first, second;
     
    public pair(int first, int second) 
    {
        this.first = first;
        this.second = second;
    }   
}
 
static final int ROW = 4;
static final int COL = 4;
 
// Direction vectors
static int dRow[] = { -1, 0, 1, 0 };
static int dCol[] = { 0, 1, 0, -1 };
 
// Function to check if a cell
// is be visited or not
static boolean isValid(boolean vis[][],
                       int row, int col)
{
     
    // If cell lies out of bounds
    if (row < 0 || col < 0 ||
        row >= ROW || col >= COL)
        return false;
 
    // If cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise
    return true;
}
 
// Function to perform the BFS traversal
static void BFS(int grid[][], boolean vis[][],
                int row, int col)
{
     
    // Stores indices of the matrix cells
    Queue<pair > q = new LinkedList<>();
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.add(new pair(row, col));
    vis[row][col] = true;
 
    // Iterate while the queue
    // is not empty
    while (!q.isEmpty())
    {
        pair cell = q.peek();
        int x = cell.first;
        int y = cell.second;
 
        System.out.print(grid[x][y] + " ");
 
        q.remove();
 
        // Go to the adjacent cells
        for(int i = 0; i < 4; i++)
        {
            int adjx = x + dRow[i];
            int adjy = y + dCol[i];
 
            if (isValid(vis, adjx, adjy))
            {
                q.add(new pair(adjx, adjy));
                vis[adjx][adjy] = true;
            }
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given input matrix
    int grid[][] = { { 1, 2, 3, 4 },
                     { 5, 6, 7, 8 },
                     { 9, 10, 11, 12 },
                     { 13, 14, 15, 16 } };
 
    // Declare the visited array
    boolean [][]vis = new boolean[ROW][COL];
 
    BFS(grid, vis, 0, 0);
}
}
 
// This code is contributed by 29AjayKumar

# Python3 program for the above approach
from collections import deque as queue
 
# Direction vectors
dRow = [ -1, 0, 1, 0]
dCol = [ 0, 1, 0, -1]
 
# Function to check if a cell
# is be visited or not
def isValid(vis, row, col):
   
    # If cell lies out of bounds
    if (row < 0 or col < 0 or row >= 4 or col >= 4):
        return False
 
    # If cell is already visited
    if (vis[row][col]):
        return False
 
    # Otherwise
    return True
 
# Function to perform the BFS traversal
def BFS(grid, vis, row, col):
   
    # Stores indices of the matrix cells
    q = queue()
 
    # Mark the starting cell as visited
    # and push it into the queue
    q.append(( row, col ))
    vis[row][col] = True
 
    # Iterate while the queue
    # is not empty
    while (len(q) > 0):
        cell = q.popleft()
        x = cell[0]
        y = cell[1]
        print(grid[x][y], end = " ")
 
        #q.pop()
 
        # Go to the adjacent cells
        for i in range(4):
            adjx = x + dRow[i]
            adjy = y + dCol[i]
            if (isValid(vis, adjx, adjy)):
                q.append((adjx, adjy))
                vis[adjx][adjy] = True
 
# Driver Code
if __name__ == '__main__':
   
    # Given input matrix
    grid= [ [ 1, 2, 3, 4 ],
           [ 5, 6, 7, 8 ],
           [ 9, 10, 11, 12 ],
           [ 13, 14, 15, 16 ] ]
 
    # Declare the visited array
    vis = [[ False for i in range(4)] for i in range(4)]
    # vis, False, sizeof vis)
 
    BFS(grid, vis, 0, 0)
 
# This code is contributed by mohit kumar 29.

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
  class pair
  {
    public int first, second;
 
    public pair(int first, int second) 
    {
      this.first = first;
      this.second = second;
    }   
  }
  static readonly int ROW = 4;
  static readonly int COL = 4;
 
  // Direction vectors
  static int []dRow = { -1, 0, 1, 0 };
  static int []dCol = { 0, 1, 0, -1 };
 
  // Function to check if a cell
  // is be visited or not
  static bool isValid(bool [,]vis,
                      int row, int col)
  {
 
    // If cell lies out of bounds
    if (row < 0 || col < 0 ||
        row >= ROW || col >= COL)
      return false;
 
    // If cell is already visited
    if (vis[row,col])
      return false;
 
    // Otherwise
    return true;
  }
 
  // Function to perform the BFS traversal
  static void BFS(int [,]grid, bool [,]vis,
                  int row, int col)
  {
 
    // Stores indices of the matrix cells
    Queue<pair> q = new Queue<pair>();
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.Enqueue(new pair(row, col));
    vis[row,col] = true;
 
    // Iterate while the queue
    // is not empty
    while (q.Count!=0)
    {
      pair cell = q.Peek();
      int x = cell.first;
      int y = cell.second;
      Console.Write(grid[x,y] + " ");
      q.Dequeue();
 
      // Go to the adjacent cells
      for(int i = 0; i < 4; i++)
      {
        int adjx = x + dRow[i];
        int adjy = y + dCol[i];
        if (isValid(vis, adjx, adjy))
        {
          q.Enqueue(new pair(adjx, adjy));
          vis[adjx,adjy] = true;
        }
      }
    }
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Given input matrix
    int [,]grid = { { 1, 2, 3, 4 },
                   { 5, 6, 7, 8 },
                   { 9, 10, 11, 12 },
                   { 13, 14, 15, 16 } };
 
    // Declare the visited array
    bool [,]vis = new bool[ROW,COL];
    BFS(grid, vis, 0, 0);
  }
}
 
// This code is contributed by 29AjayKumar

<script>
 
// Javascript program for the above approach
 
var ROW = 4;
var COL = 4;
 
// Direction vectors
var dRow = [-1, 0, 1, 0 ];
var dCol = [0, 1, 0, -1 ];
 
// Function to check if a cell
// is be visited or not
function isValid(vis, row, col)
{
    // If cell lies out of bounds
    if (row < 0 || col < 0
        || row >= ROW || col >= COL)
        return false;
 
    // If cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise
    return true;
}
 
// Function to perform the BFS traversal
function BFS( grid, vis,row, col)
{
    // Stores indices of the matrix cells
    var q = [];
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.push([row, col ]);
    vis[row][col] = true;
 
    // Iterate while the queue
    // is not empty
    while (q.length!=0) {
 
        var cell = q[0];
        var x = cell[0];
        var y = cell[1];
 
        document.write( grid[x][y] + " ");
 
        q.shift();
 
        // Go to the adjacent cells
        for (var i = 0; i < 4; i++) {
 
            var adjx = x + dRow[i];
            var adjy = y + dCol[i];
 
            if (isValid(vis, adjx, adjy)) {
                q.push([adjx, adjy ]);
                vis[adjx][adjy] = true;
            }
        }
    }
}
 
// Driver Code
// Given input matrix
var grid = [[1, 2, 3, 4 ],
                       [5, 6, 7, 8 ],
                       [9, 10, 11, 12 ],
                       [13, 14, 15, 16 ] ];
// Declare the visited array
var vis = Array.from(Array(ROW), ()=> Array(COL).fill(false));
BFS(grid, vis, 0, 0);
 
 
</script>

1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16

Complejidad de Tiempo: O(N * M)
Espacio Auxiliar: O(N * M)