Profundidad de primer recorrido (DFS) en una array 2D

Dada una cuadrícula de arreglo 2D [][] de dimensión N * M , la tarea es realizar el recorrido Profundidad – Primera búsqueda en el arreglo 2D dado .

Ejemplos:

Entrada:  grid[][] = {{-1, 2, 3}, {0, 9, 8}, {1, 0, 1}}
Salida:  -1 2 3 8 1 0 9 0 1
Explicación: La secuencia de recorrido de elementos de array usando DFS es -1, 2, 3, 8, 1, 0, 9, 0, 1. 

Entrada: grid[][] = {{1, 2, 3}, {5, 6, 7}, {9, 10, 11}}
Salida: 1 2 3 7 11 10 6 5 9

 

Enfoque: la idea es utilizar la estructura de datos de pila para realizar DFS transversal en la array 2D . Siga los pasos a continuación para resolver el problema dado:

  • Inicialice una pila , digamos S, con las coordenadas de la celda inicial como (0, 0) .
  • Inicialice una array 2D booleana auxiliar de dimensión N * M con todos los valores como false , que se utiliza para marcar las celdas visitadas.
  • 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.
  • Iterar mientras la pila no está vacía y realizar los siguientes pasos:
    • Extraiga la celda presente en la parte superior de la pila e imprima el elemento en esa celda.
    • Empuje la celda adyacente a las celdas emergentes anteriores en la pila, si son válidas al verificar usando la función isValid() .

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++

// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
#define ROW 3
#define COL 3
 
// Initialize direction vectors
int dRow[] = { 0, 1, 0, -1 };
int dCol[] = { -1, 0, 1, 0 };
 
// Function to check if mat[row][col]
// is unvisited and lies within the
// boundary of the given matrix
bool isValid(bool vis[][COL],
             int row, int col)
{
    // If cell is out of bounds
    if (row < 0 || col < 0
        || row >= ROW || col >= COL)
        return false;
 
    // If the cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise, it can be visited
    return true;
}
 
// Function to perform DFS
// Traversal on the matrix grid[]
void DFS(int row, int col,
         int grid[][COL],
         bool vis[][COL])
{
    // Initialize a stack of pairs and
    // push the starting cell into it
    stack<pair<int, int> > st;
    st.push({ row, col });
 
    // Iterate until the
    // stack is not empty
    while (!st.empty()) {
        // Pop the top pair
        pair<int, int> curr = st.top();
        st.pop();
        int row = curr.first;
        int col = curr.second;
 
        // Check if the current popped
        // cell is a valid cell or not
        if (!isValid(vis, row, col))
            continue;
 
        // Mark the current
        // cell as visited
        vis[row][col] = true;
 
        // Print the element at
        // the current top cell
        cout << grid[row][col] << " ";
 
        // Push all the adjacent cells
        for (int i = 0; i < 4; i++) {
            int adjx = row + dRow[i];
            int adjy = col + dCol[i];
            st.push({ adjx, adjy });
        }
    }
}
 
// Driver Code
int main()
{
    int grid[ROW][COL] = { { -1, 2, 3 },
                           { 0, 9, 8 },
                           { 1, 0, 1 } };
 
    // Stores whether the current
    // cell is visited or not
    bool vis[ROW][COL];
    memset(vis, false, sizeof vis);
 
    // Function call
    DFS(0, 0, grid, vis);
 
    return 0;
}

Java

// Java program of the above approach
import java.util.Stack;
 
class GFG{
     
static int ROW = 3;
static int COL = 3;
 
// Initialize direction vectors
static int dRow[] = { 0, 1, 0, -1 };
static int dCol[] = { -1, 0, 1, 0 };
 
static class pair
{
    public int first;
    public int second;
 
    public pair(int first, int second)
    {
        this.first = first;
        this.second = second;
    }
}
 
static Boolean isValid(Boolean vis[][], int row,
                                        int col)
{
     
    // If cell is out of bounds
    if (row < 0 || col < 0 ||
        row >= ROW || col >= COL)
        return false;
 
    // If the cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise, it can be visited
    return true;
}
 
// Function to perform DFS
// Traversal on the matrix grid[]
static void DFS(int row, int col, int grid[][],
                               Boolean vis[][])
{
     
    // Initialize a stack of pairs and
    // push the starting cell into it
    Stack<pair> st = new Stack<pair>();
    st.push(new pair(row, col));
 
    // Iterate until the
    // stack is not empty
    while (!st.empty())
    {
         
        // Pop the top pair
        pair curr = st.pop();
 
        row = curr.first;
        col = curr.second;
 
        // Check if the current popped
        // cell is a valid cell or not
        if (!isValid(vis, row, col))
            continue;
 
        // Mark the current
        // cell as visited
        vis[row][col] = true;
 
        // Print the element at
        // the current top cell
        System.out.print(grid[row][col] + " ");
 
        // Push all the adjacent cells
        for(int i = 0; i < 4; i++)
        {
            int adjx = row + dRow[i];
            int adjy = col + dCol[i];
            st.push(new pair(adjx, adjy));
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
    int grid[][] = { { -1, 2, 3 },
                     { 0, 9, 8 },
                     { 1, 0, 1 } };
                      
    Boolean vis[][] = new Boolean[ROW][COL];
    for(int i = 0; i < ROW; i++)
    {
        for(int j = 0; j < COL; j++)
        {
            vis[i][j] = false;
        }
    }
     
    // Function call
    DFS(0, 0, grid, vis);
}
}
 
// This code is contributed by abhinavjain194

Python3

# Python 3 program of the above approach
ROW = 3
COL = 3
 
# Initialize direction vectors
dRow = [0, 1, 0, -1]
dCol = [-1, 0, 1, 0]
vis = [[False for i in range(3)] for j in range(3)]
 
# Function to check if mat[row][col]
# is unvisited and lies within the
# boundary of the given matrix
def isValid(row, col):
    global ROW
    global COL
    global vis
     
    # If cell is out of bounds
    if (row < 0 or col < 0 or row >= ROW or col >= COL):
        return False
 
    # If the cell is already visited
    if (vis[row][col]):
        return False
 
    # Otherwise, it can be visited
    return True
 
# Function to perform DFS
# Traversal on the matrix grid[]
def DFS(row, col, grid):
    global dRow
    global dCol
    global vis
     
    # Initialize a stack of pairs and
    # push the starting cell into it
    st = []
    st.append([row, col])
 
    # Iterate until the
    # stack is not empty
    while (len(st) > 0):
        # Pop the top pair
        curr = st[len(st) - 1]
        st.remove(st[len(st) - 1])
        row = curr[0]
        col = curr[1]
 
        # Check if the current popped
        # cell is a valid cell or not
        if (isValid(row, col) == False):
            continue
 
        # Mark the current
        # cell as visited
        vis[row][col] = True
 
        # Print the element at
        # the current top cell
        print(grid[row][col], end = " ")
 
        # Push all the adjacent cells
        for i in range(4):
            adjx = row + dRow[i]
            adjy = col + dCol[i]
            st.append([adjx, adjy])
 
# Driver Code
if __name__ == '__main__':
    grid =  [[-1, 2, 3],
             [0, 9, 8],
             [1, 0, 1]]
 
    # Function call
    DFS(0, 0, grid)
     
    # This code is contributed by SURENDRA_GANGWAR.

C#

// C# program of the above approach
using System;
using System.Collections;
 
class GFG{
     
static int ROW = 3;
static int COL = 3;
  
// Initialize direction vectors
static int[] dRow = { 0, 1, 0, -1 };
static int[] dCol = { -1, 0, 1, 0 };
 
static bool isValid(bool[,] vis, int row, int col)
{
     
    // If cell is out of bounds
    if (row < 0 || col < 0 ||
        row >= ROW || col >= COL)
        return false;
  
    // If the cell is already visited
    if (vis[row,col])
        return false;
  
    // Otherwise, it can be visited
    return true;
}
  
// Function to perform DFS
// Traversal on the matrix grid[]
static void DFS(int row, int col,
                int[,] grid, bool[,] vis)
{
     
    // Initialize a stack of pairs and
    // push the starting cell into it
    Stack st = new Stack();
    st.Push(new Tuple<int, int>(row, col));
  
    // Iterate until the
    // stack is not empty
    while (st.Count > 0)
    {
         
        // Pop the top pair
        Tuple<int, int> curr = (Tuple<int, int>)st.Peek();
        st.Pop();
  
        row = curr.Item1;
        col = curr.Item2;
  
        // Check if the current popped
        // cell is a valid cell or not
        if (!isValid(vis, row, col))
            continue;
  
        // Mark the current
        // cell as visited
        vis[row, col] = true;
  
        // Print the element at
        // the current top cell
        Console.Write(grid[row, col] + " ");
  
        // Push all the adjacent cells
        for(int i = 0; i < 4; i++)
        {
            int adjx = row + dRow[i];
            int adjy = col + dCol[i];
            st.Push(new Tuple<int, int>(adjx, adjy));
        }
    }
}
 
// Driver code
static void Main()
{
    int[,] grid = { { -1, 2, 3 },
                    { 0, 9, 8 },
                    { 1, 0, 1 } };
           
    bool[,] vis = new bool[ROW, COL];
    for(int i = 0; i < ROW; i++)
    {
        for(int j = 0; j < COL; j++)
        {
            vis[i, j] = false;
        }
    }
     
    // Function call
    DFS(0, 0, grid, vis);
}
}
 
// This code is contributed by mukesh07

Javascript

<script>
 
// Javascript program of the above approach
var ROW = 3;
var COL = 3
 
// Initialize direction vectors
var dRow = [0, 1, 0, -1];
var dCol = [ -1, 0, 1, 0];
 
// Function to check if mat[row][col]
// is unvisited and lies within the
// boundary of the given matrix
function isValid(vis, row, col)
{
    // If cell is out of bounds
    if (row < 0 || col < 0
        || row >= ROW || col >= COL)
        return false;
 
    // If the cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise, it can be visited
    return true;
}
 
// Function to perform DFS
// Traversal on the matrix grid[]
function DFS(row, col,grid, vis)
{
    // Initialize a stack of pairs and
    // push the starting cell into it
    var st = [];
    st.push([ row, col ]);
 
    // Iterate until the
    // stack is not empty
    while (st.length!=0) {
        // Pop the top pair
        var curr = st[st.length-1];
        st.pop();
        var row = curr[0];
        var col = curr[1];
 
        // Check if the current popped
        // cell is a valid cell or not
        if (!isValid(vis, row, col))
            continue;
 
        // Mark the current
        // cell as visited
        vis[row][col] = true;
 
        // Print the element at
        // the current top cell
        document.write( grid[row][col] + " ");
 
        // Push all the adjacent cells
        for (var i = 0; i < 4; i++) {
            var adjx = row + dRow[i];
            var adjy = col + dCol[i];
            st.push([ adjx, adjy ]);
        }
    }
}
 
// Driver Code
var grid = [ [ -1, 2, 3 ],
                       [ 0, 9, 8 ],
                       [ 1, 0, 1 ] ];
// Stores whether the current
// cell is visited or not
var vis = Array.from(Array(ROW), ()=> Array(COL).fill(false));
// Function call
DFS(0, 0, grid, vis);
 
 
</script>
Producción: 

-1 2 3 8 1 0 9 0 1

 

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

Publicación traducida automáticamente

Artículo escrito por ramandeep8421 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 *