Dada una cuadrícula de array [][] con dimensión M × N de enteros, la tarea es imprimir los elementos de la array utilizando DFS transversal .
Ejemplos:
Entrada: mat[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}
Salida : 1 2 3 4 8 12 16 15 11 7 6 10 14 13 9 5
Explicación: Los elementos de la array en el orden de su recorrido de búsqueda en profundidad primero son 1 2 3 4 8 12 16 15 11 7 6 10 14 13 9 5.Entrada: mat[][] = {{0, 1, 9, 4}, {1, 2, 3, 4}, {0, 0, -1, -1}, {-1, -1, 0, 1}}
Salida: 0 1 9 4 4 -1 1 0 -1 3 2 0 -1 -1 0 1
Enfoque recursivo : la idea es utilizar una búsqueda recursiva en profundidad para atravesar la array e imprimir sus elementos. Siga los pasos a continuación para resolver el problema:
- Inicialice un vector booleano 2D , digamos vis[][] , para realizar un seguimiento de los índices ya visitados y no visitados.
- Defina una función, digamos isValid(i, j) , para verificar si la posición (i, j) es válida o no, es decir , (i, j) debe estar dentro de la array y no debe visitarse.
- Defina una función recursiva DFS(i, j):
- En cada llamada, marque la posición actual (i, j) visitada e imprima el elemento en esa posición.
- Realice la llamada recursiva para todos los lados adyacentes, es decir, DFS(i + 1, j), DFS(i, j + 1), DFS(i – 1, j) y DFS(i, j – 1) si las posiciones respectivas son válidos, es decir, no visitados y están dentro de la array .
- Finalmente, llame a la función DFS(0, 0) para iniciar el DFS Traversal para imprimir la array .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Direction vectors
int dRow[] = { -1, 0, 1, 0 };
int dCol[] = { 0, 1, 0, -1 };
// Function to check if current
// position is valid or not
bool isValid(vector<vector<bool> >& vis,
int row, int col,
int COL, int ROW)
{
// Check if the cell is out of bounds
if (row < 0 || col < 0 || col > COL - 1
|| row > ROW - 1)
return false;
// Check if the cell is visited or not
if (vis[row][col] == true)
return false;
return true;
}
// Utility function to print matrix
// elements using DFS Traversal
void DFSUtil(int row, int col,
vector<vector<int> > grid,
vector<vector<bool> >& vis,
int M, int N)
{
// Mark the current cell visited
vis[row][col] = true;
// Print the element at the cell
cout << grid[row][col] << " ";
// Traverse all four adjacent
// cells of the current element
for (int i = 0; i < 4; i++) {
int x = row + dRow[i];
int y = col + dCol[i];
// Check if x and y is
// valid index or not
if (isValid(vis, x, y, M, N))
DFSUtil(x, y, grid, vis, M, N);
}
}
// Function to print the matrix elements
void DFS(int row, int col,
vector<vector<int> > grid,
int M, int N)
{
// Initialize a visiting matrix
vector<vector<bool> > vis(
M + 1, vector<bool>(N + 1, false));
// Function call to print matrix
// elements by DFS traversal
DFSUtil(0, 0, grid, vis, M, N);
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > grid{ { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Row of the matrix
int M = grid.size();
// Column of the matrix
int N = grid[0].size();
DFS(0, 0, grid, M, N);
return 0;
}
Java
// Java program to implement
// the above approach
import java.util.*;
class GFG
{
// Direction vectors
static int dRow[] = { -1, 0, 1, 0 };
static int dCol[] = { 0, 1, 0, -1 };
// Function to check if current
// position is valid or not
static boolean isValid(boolean[][] vis,
int row, int col,
int COL, int ROW)
{
// Check if the cell is out of bounds
if (row < 0 || col < 0 || col > COL - 1
|| row > ROW - 1)
return false;
// Check if the cell is visited or not
if (vis[row][col] == true)
return false;
return true;
}
// Utility function to print matrix
// elements using DFS Traversal
static void DFSUtil(int row, int col,
int[][] grid,
boolean[][] vis,
int M, int N)
{
// Mark the current cell visited
vis[row][col] = true;
// Print the element at the cell
System.out.print(grid[row][col] + " ");
// Traverse all four adjacent
// cells of the current element
for (int i = 0; i < 4; i++) {
int x = row + dRow[i];
int y = col + dCol[i];
// Check if x and y is
// valid index or not
if (isValid(vis, x, y, M, N))
DFSUtil(x, y, grid, vis, M, N);
}
}
// Function to print the matrix elements
static void DFS(int row, int col,
int[][] grid,
int M, int N)
{
// Initialize a visiting matrix
boolean[][] vis = new boolean[M + 1][N + 1];
for(int i = 0; i < M + 1; i++)
{
for(int j = 0; j < N + 1; j++)
{
vis[i][j] = false;
}
}
// Function call to print matrix
// elements by DFS traversal
DFSUtil(0, 0, grid, vis, M, N);
}
// Driver Code
public static void main(String args[])
{
// Given matrix
int[][] grid = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Row of the matrix
int M = grid.length;
// Column of the matrix
int N = grid[0].length;
DFS(0, 0, grid, M, N);
}
}
// This code is contributed by susmitakundugoaldanga.
Python3
# Python3 program for the above approach # Direction vectors dRow = [-1, 0, 1, 0] dCol = [0, 1, 0, -1] # Function to check if current # position is valid or not def isValid(row, col, COL, ROW): global vis # Check if the cell is out of bounds if (row < 0 or col < 0 or col > COL - 1 or row > ROW - 1): return False # Check if the cell is visited or not if (vis[row][col] == True): return False return True # Utility function to print matrix # elements using DFS Traversal def DFSUtil(row, col,grid, M, N): global vis # Mark the current cell visited vis[row][col] = True # Print element at the cell print(grid[row][col], end = " ") # Traverse all four adjacent # cells of the current element for i in range(4): x = row + dRow[i] y = col + dCol[i] # Check if x and y is # valid index or not if (isValid(x, y, M, N)): DFSUtil(x, y, grid, M, N) # Function to print matrix elementsdef def DFS(row, col,grid, M, N): global vis # Initialize a visiting matrix # Function call to print matrix # elements by DFS traversal DFSUtil(0, 0, grid, M, N) # Driver Code if __name__ == '__main__': # Given matrix grid = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ] # Row of the matrix M = len(grid) # Column of the matrix N = len(grid[0]) vis = [[False for i in range(M)] for i in range(N)] DFS(0, 0, grid, M, N) # This code is contributed by mohit kumar 29.
C#
// C# program to implement
// the above approach
using System;
public class GFG
{
// Direction vectors
static int []dRow = { -1, 0, 1, 0 };
static int []dCol = { 0, 1, 0, -1 };
// Function to check if current
// position is valid or not
static bool isValid(bool[,] vis,
int row, int col,
int COL, int ROW)
{
// Check if the cell is out of bounds
if (row < 0 || col < 0 || col > COL - 1
|| row > ROW - 1)
return false;
// Check if the cell is visited or not
if (vis[row,col] == true)
return false;
return true;
}
// Utility function to print matrix
// elements using DFS Traversal
static void DFSUtil(int row, int col,
int[,] grid,
bool[,] vis,
int M, int N)
{
// Mark the current cell visited
vis[row,col] = true;
// Print the element at the cell
Console.Write(grid[row,col] + " ");
// Traverse all four adjacent
// cells of the current element
for (int i = 0; i < 4; i++) {
int x = row + dRow[i];
int y = col + dCol[i];
// Check if x and y is
// valid index or not
if (isValid(vis, x, y, M, N))
DFSUtil(x, y, grid, vis, M, N);
}
}
// Function to print the matrix elements
static void DFS(int row, int col,
int[,] grid,
int M, int N)
{
// Initialize a visiting matrix
bool[,] vis = new bool[M + 1,N + 1];
for(int i = 0; i < M + 1; i++)
{
for(int j = 0; j < N + 1; j++)
{
vis[i,j] = false;
}
}
// Function call to print matrix
// elements by DFS traversal
DFSUtil(0, 0, grid, vis, M, N);
}
// Driver Code
public static void Main(String []args)
{
// Given matrix
int[,] grid = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Row of the matrix
int M = grid.GetLength(0);
// Column of the matrix
int N = grid.GetLength(1);
DFS(0, 0, grid, M, N);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program of the above approach
// Direction vectors
let dRow = [ -1, 0, 1, 0 ];
let dCol = [ 0, 1, 0, -1 ];
// Function to check if current
// position is valid or not
function isValid(vis, row, col,
COL, ROW)
{
// Check if the cell is out of bounds
if (row < 0 || col < 0 || col > COL - 1
|| row > ROW - 1)
return false;
// Check if the cell is visited or not
if (vis[row][col] == true)
return false;
return true;
}
// Utility function to print matrix
// elements using DFS Traversal
function DFSUtil(row, col, grid,
vis, M, N)
{
// Mark the current cell visited
vis[row][col] = true;
// Print the element at the cell
document.write(grid[row][col] + " ");
// Traverse all four adjacent
// cells of the current element
for (let i = 0; i < 4; i++) {
let x = row + dRow[i];
let y = col + dCol[i];
// Check if x and y is
// valid index or not
if (isValid(vis, x, y, M, N))
DFSUtil(x, y, grid, vis, M, N);
}
}
// Function to print the matrix elements
function DFS(row, col, grid, M, N)
{
// Initialize a visiting matrix
let vis = new Array(M + 1);
// Loop to create 2D array using 1D array
for (var i = 0; i < vis.length; i++) {
vis[i] = new Array(2);
}
for(let i = 0; i < M + 1; i++)
{
for(let j = 0; j < N + 1; j++)
{
vis[i][j] = false;
}
}
// Function call to print matrix
// elements by DFS traversal
DFSUtil(0, 0, grid, vis, M, N);
}
// Driver Code
// Given matrix
let grid = [[ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ]];
// Row of the matrix
let M = grid.length;
// Column of the matrix
let N = grid[0].length;
DFS(0, 0, grid, M, N);
</script>
Producción
1 2 3 4 8 12 16 15 11 7 6 10 14 13 9 5
Complejidad temporal: O(N*M)
Espacio auxiliar: O(N*M)
Enfoque iterativo: la idea es atravesar la array utilizando una búsqueda iterativa en profundidad e imprimir los elementos de la array. Siga los pasos a continuación para resolver el problema:
- Defina una función, digamos isValid(i, j) , para comprobar si la posición (i, j) es válida o no, es decir, (i, j) se encuentra dentro de la array y no se visita.
- Inicialice un vector booleano 2d , digamos vis[][] , para realizar un seguimiento de una posición, digamos (i, j) , ya sea que haya sido visitada o no.
- Inicialice un stack<pair<int, int>> say S para implementar el recorrido DFS.
- Primero empuje la primera celda (0, 0) en la pila S marcando la celda visitada.
- Iterar mientras la pila S no está vacía:
- En cada iteración, marque el elemento superior de la pila, digamos (i, j) visitado e imprima el elemento en esa posición y elimine el elemento superior de la pila S .
- Empuje las celdas adyacentes, es decir (i + 1, j), (i, j + 1), (i – 1, j) y (i, j – 1) en la pila si las posiciones respectivas son válidas, es decir, no visitadas y son dentro de la array.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Direction vectors
int dRow[] = { -1, 0, 1, 0 };
int dCol[] = { 0, 1, 0, -1 };
// Function to check if curruent
// position is valid or not
bool isValid(vector<vector<bool> >& vis,
int row, int col,
int COL, int ROW)
{
// Check if the cell is out
// of bounds
if (row < 0 || col < 0 || col > COL - 1
|| row > ROW - 1)
return false;
// Check if the cell is visited
if (vis[row][col] == true)
return false;
return true;
}
// Function to print the matrix elements
void DFS_iterative(vector<vector<int> > grid,
int M, int N)
{
// Stores if a position in the
// matrix been visited or not
vector<vector<bool> > vis(
M + 5, vector<bool>(N + 5, false));
// Initialize stack to implement DFS
stack<pair<int, int> > st;
// Push the first position of grid[][]
// in the stack
st.push({ 0, 0 });
// Mark the cell (0, 0) visited
vis[0][0] = true;
while (!st.empty()) {
// Stores top element of stack
pair<int, int> p = st.top();
// Delete the top() element
// of stack
st.pop();
int row = p.first;
int col = p.second;
// Print element at the cell
cout << grid[row][col] << " ";
// Traverse in all four adjacent
// sides of current positions
for (int i = 0; i < 4; i++) {
int x = row + dRow[i];
int y = col + dCol[i];
// Check if x and y is valid
// position and then push
// the position of current
// cell in the stack
if (isValid(vis, x, y, M, N)) {
// Push the current cell
st.push({ x, y });
// Mark current cell visited
vis[x][y] = true;
}
}
}
}
// Driver Code
int main()
{
// Given matrix
vector<vector<int> > grid{ { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Row of the matrix
int M = grid.size();
// Column of the matrix
int N = grid[0].size();
DFS_iterative(grid, M, N);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
public class Main
{
public static class Pair {
int Item1, Item2;
public Pair(int Item1, int Item2) {
this.Item1 = Item1;
this.Item2 = Item2;
}
}
// Direction vectors
static int[] dRow = { -1, 0, 1, 0 };
static int[] dCol = { 0, 1, 0, -1 };
static Vector<Vector<Boolean>> vis;
// Function to check if curruent
// position is valid or not
static boolean isValid(int row, int col, int COL, int ROW)
{
// Check if the cell is out
// of bounds
if (row < 0 || col < 0 || col > COL - 1 || row > ROW - 1)
return false;
// Check if the cell is visited
if (vis.get(row).get(col) == true)
return false;
return true;
}
// Function to print the matrix elements
static void DFS_iterative(int[][] grid, int M, int N)
{
// Stores if a position in the
// matrix been visited or not
vis = new Vector<Vector<Boolean>>();
for(int i = 0; i < M + 5; i++)
{
vis.add(new Vector<Boolean>());
for(int j = 0; j < N + 5; j++)
{
vis.get(i).add(false);
}
}
// Initialize stack to implement DFS
Vector<Pair> st = new Vector<Pair>();
// Push the first position of grid[][]
// in the stack
st.add(new Pair(0, 0));
// Mark the cell (0, 0) visited
vis.get(0).set(0, true);
while (st.size() > 0) {
// Stores top element of stack
Pair p = st.get(st.size() - 1);
// Delete the top() element
// of stack
st.remove(st.size() - 1);
int row = p.Item1;
int col = p.Item2;
// Print element at the cell
System.out.print(grid[row][col] + " ");
// Traverse in all four adjacent
// sides of current positions
for (int i = 0; i < 4; i++) {
int x = row + dRow[i];
int y = col + dCol[i];
// Check if x and y is valid
// position and then push
// the position of current
// cell in the stack
if (isValid(x, y, M, N)) {
// Push the current cell
st.add(new Pair(x, y));
// Mark current cell visited
vis.get(x).set(y, true);
}
}
}
}
public static void main(String[] args)
{
// Given matrix
int[][] grid = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Row of the matrix
int M = 4;
// Column of the matrix
int N = 4;
DFS_iterative(grid, M, N);
}
}
// This code is contributed by suresh07.
Python3
# Python3 program for the above approach # Direction vectors dRow = [ -1, 0, 1, 0 ] dCol = [ 0, 1, 0, -1 ] vis = [] # Function to check if curruent # position is valid or not def isValid(row, col, COL, ROW): global vis # Check if the cell is out # of bounds if (row < 0 or col < 0 or col > COL - 1 or row > ROW - 1): return False # Check if the cell is visited if (vis[row][col] == True): return False return True # Function to print the matrix elements def DFS_iterative(grid, M, N): global vis # Stores if a position in the # matrix been visited or not vis = [] for i in range(M+5): vis.append([]) for j in range(N + 5): vis[i].append(False) # Initialize stack to implement DFS st = [] # Push the first position of grid[][] # in the stack st.append([ 0, 0 ]) # Mark the cell (0, 0) visited vis[0][0] = True while (len(st) > 0): # Stores top element of stack p = st[-1] # Delete the top() element # of stack st.pop() row = p[0] col = p[1] # Print element at the cell print(grid[row][col], "", end = "") # Traverse in all four adjacent # sides of current positions for i in range(4): x = row + dRow[i] y = col + dCol[i] # Check if x and y is valid # position and then push # the position of current # cell in the stack if (isValid(x, y, M, N)): # Push the current cell st.append([ x, y ]) # Mark current cell visited vis[x][y] = True # Given matrix grid = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ] # Row of the matrix M = len(grid) # Column of the matrix N = len(grid[0]) DFS_iterative(grid, M, N) # This code is contributed by mukesh07.
C#
// C# program for the above approach
using System;
using System.Collections.Generic;
class GFG {
// Direction vectors
static int[] dRow = { -1, 0, 1, 0 };
static int[] dCol = { 0, 1, 0, -1 };
static List<List<bool>> vis;
// Function to check if curruent
// position is valid or not
static bool isValid(int row, int col, int COL, int ROW)
{
// Check if the cell is out
// of bounds
if (row < 0 || col < 0 || col > COL - 1 || row > ROW - 1)
return false;
// Check if the cell is visited
if (vis[row][col] == true)
return false;
return true;
}
// Function to print the matrix elements
static void DFS_iterative(int[,] grid, int M, int N)
{
// Stores if a position in the
// matrix been visited or not
vis = new List<List<bool>>();
for(int i = 0; i < M + 5; i++)
{
vis.Add(new List<bool>());
for(int j = 0; j < N + 5; j++)
{
vis[i].Add(false);
}
}
// Initialize stack to implement DFS
List<Tuple<int,int>> st = new List<Tuple<int,int>>();
// Push the first position of grid[][]
// in the stack
st.Add(new Tuple<int,int>(0, 0));
// Mark the cell (0, 0) visited
vis[0][0] = true;
while (st.Count > 0) {
// Stores top element of stack
Tuple<int,int> p = st[st.Count - 1];
// Delete the top() element
// of stack
st.RemoveAt(st.Count - 1);
int row = p.Item1;
int col = p.Item2;
// Print element at the cell
Console.Write(grid[row,col] + " ");
// Traverse in all four adjacent
// sides of current positions
for (int i = 0; i < 4; i++) {
int x = row + dRow[i];
int y = col + dCol[i];
// Check if x and y is valid
// position and then push
// the position of current
// cell in the stack
if (isValid(x, y, M, N)) {
// Push the current cell
st.Add(new Tuple<int,int>(x, y));
// Mark current cell visited
vis[x][y] = true;
}
}
}
}
static void Main()
{
// Given matrix
int[,] grid = { { 1, 2, 3, 4 },
{ 5, 6, 7, 8 },
{ 9, 10, 11, 12 },
{ 13, 14, 15, 16 } };
// Row of the matrix
int M = 4;
// Column of the matrix
int N = 4;
DFS_iterative(grid, M, N);
}
}
// This code is contributed by divyesh072019.
Javascript
<script>
// Javascript program for the above approach
// Direction vectors
let dRow = [ -1, 0, 1, 0 ];
let dCol = [ 0, 1, 0, -1 ];
let vis;
// Function to check if curruent
// position is valid or not
function isValid(row, col,
COL, ROW)
{
// Check if the cell is out
// of bounds
if (row < 0 || col < 0 || col > COL - 1
|| row > ROW - 1)
return false;
// Check if the cell is visited
if (vis[row][col] == true)
return false;
return true;
}
// Function to print the matrix elements
function DFS_iterative(grid, M, N)
{
// Stores if a position in the
// matrix been visited or not
vis = [];
for(let i = 0; i < M + 5; i++)
{
vis.push([]);
for(let j = 0; j < N + 5; j++)
{
vis[i].push(false);
}
}
// Initialize stack to implement DFS
let st = [];
// Push the first position of grid[][]
// in the stack
st.push([ 0, 0 ]);
// Mark the cell (0, 0) visited
vis[0][0] = true;
while (st.length > 0) {
// Stores top element of stack
let p = st[st.length - 1];
// Delete the top() element
// of stack
st.pop();
let row = p[0];
let col = p[1];
// Print element at the cell
document.write(grid[row][col] + " ");
// Traverse in all four adjacent
// sides of current positions
for (let i = 0; i < 4; i++) {
let x = row + dRow[i];
let y = col + dCol[i];
// Check if x and y is valid
// position and then push
// the position of current
// cell in the stack
if (isValid(x, y, M, N)) {
// Push the current cell
st.push([ x, y ]);
// Mark current cell visited
vis[x][y] = true;
}
}
}
}
// Given matrix
let grid = [ [ 1, 2, 3, 4 ],
[ 5, 6, 7, 8 ],
[ 9, 10, 11, 12 ],
[ 13, 14, 15, 16 ] ];
// Row of the matrix
let M = grid.length;
// Column of the matrix
let N = grid[0].length;
DFS_iterative(grid, M, N);
// This code is contributed by decode2207.
</script>
Producción:
1 5 9 13 14 15 16 12 8 7 3 4 11 10 6 2
Complejidad temporal: 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