Depth First Traversal ( DFS ) on a 2D array
Given a 2D array grid[][] of dimension N * M, the task is to perform the Depth – First Search traversal on the given 2D array.
Examples:
Input: grid[][] = {{-1, 2, 3}, {0, 9, 8}, {1, 0, 1}}
Output: -1 2 3 8 1 0 9 0 1
Explanation: The sequence of traversal of matrix elements using DFS is -1, 2, 3, 8, 1, 0, 9, 0, 1.Input: grid[][] = {{1, 2, 3}, {5, 6, 7}, {9, 10, 11}}
Output: 1 2 3 7 11 10 6 5 9
Approach: The idea is to use Stack Data Structure to perform DFS Traversal on the 2D array. Follow the steps below to solve the given problem:
- Initialize a stack, say S, with the starting cell coordinates as (0, 0).
- Initialize an auxiliary boolean 2D array of dimension N * M with all values as false, which is used to mark the visited cells.
- Declare a function isValid() to check if the cell coordinates are valid or not, i.e lies within the boundaries of the given matrix and is unvisited or not.
- Iterate while the stack is not empty and perform the following steps:
- Pop the cell present at the top of the stack and print the element at that cell.
- Push the cell adjacent to the above-popped cells into the stack, if they are valid by checking using isValid() function.
Note: Direction vectors are used to traverse the adjacent cells of a given cell in a given order. For example, (x, y) is a cell whose adjacent cells (x – 1, y), (x, y + 1), (x + 1, y), (x, y – 1) need to be traversed, then it can be done using the direction vectors (-1, 0), (0, 1), (1, 0), (0, -1) in the up, left, down and right order.
Below is the implementation of the above approach:
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> |
-1 2 3 8 1 0 9 0 1
Time Complexity: O(N * M)
Auxiliary Space: O(N * M )
Contact Us