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