Given a matrix grid[][] with dimension M × N of integers, the task is to print the matrix elements using DFS traversal.
Examples:
Input: mat[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}
Output: 1 2 3 4 8 12 16 15 11 7 6 10 14 13 9 5
Explanation: The matrix elements in the order of their Depth First Search traversal are 1 2 3 4 8 12 16 15 11 7 6 10 14 13 9 5.Input: mat[][] = {{0, 1, 9, 4}, {1, 2, 3, 4}, {0, 0, -1, -1}, {-1, -1, 0, 1}}
Output: 0 1 9 4 4 -1 1 0 -1 3 2 0 -1 -1 0 1
Recursive Approach: The idea is to use a Recursive depth-first search for traversing the matrix and printing its elements. Follow the steps below to solve the problem:
- Initialize a 2D boolean vector, say vis[][], to keep track of already visited and unvisited indices.
- Define a function, say isValid(i, j), to check if the position (i, j) is valid or not i.e (i, j) should be inside the matrix and not visited.
- Define a recursive function DFS(i, j):
- On each call, mark the current position (i, j) visited and print the element at that position.
- Make the recursive call for all the adjacent sides, i.e DFS(i + 1, j), DFS(i, j + 1), DFS(i – 1, j) and DFS(i, j – 1) if respective positions are valid i.e., not visited and are within the matrix.
- Finally, call the function DFS(0, 0) to start the DFS Traversal to print the matrix.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Direction vectorsint dRow[] = { -1, 0, 1, 0 };int dCol[] = { 0, 1, 0, -1 };// Function to check if current// position is valid or notbool 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 Traversalvoid 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 elementsvoid 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 Codeint 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 vectorsstatic int dRow[] = { -1, 0, 1, 0 };static int dCol[] = { 0, 1, 0, -1 };// Function to check if current// position is valid or notstatic 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 Traversalstatic 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 elementsstatic 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 Codepublic 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 vectorsdRow = [-1, 0, 1, 0]dCol = [0, 1, 0, -1]# Function to check if current# position is valid or notdef 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 Traversaldef 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 elementsdefdef 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 Codeif __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 vectorsstatic int []dRow = { -1, 0, 1, 0 };static int []dCol = { 0, 1, 0, -1 };// Function to check if current// position is valid or notstatic 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 Traversalstatic 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 elementsstatic 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 Codepublic 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 vectorslet dRow = [ -1, 0, 1, 0 ];let dCol = [ 0, 1, 0, -1 ];// Function to check if current// position is valid or notfunction 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 Traversalfunction 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 elementsfunction 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> |
Output
1 2 3 4 8 12 16 15 11 7 6 10 14 13 9 5
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Iterative Approach: The idea is to traverse the matrix using iterative depth-first search and print the matrix elements. Follow the steps below to solve the problem:
- Define a function, say isValid(i, j), to check if the position (i, j) is valid or not, i.e (i, j) lies inside the matrix and not visited.
- Initialize a 2d boolean vector, say vis[][], for keeping track of a position say (i, j) whether it has been already visited or not.
- Initialize a stack<pair<int, int>> say S to implement the DFS traversal.
- First push the first cell (0, 0) in the stack S marking the cell visited.
- Iterate while stack S is not empty:
- In each iteration, mark the top element of stack say (i, j) visited and print the element at that position and remove the top element from the stack S.
- Push the adjacent cells i.e (i + 1, j), (i, j + 1), (i – 1, j) and (i, j – 1) into the stack if respective positions are valid i.e., not visited and are within the matrix.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Direction vectorsint dRow[] = { -1, 0, 1, 0 };int dCol[] = { 0, 1, 0, -1 };// Function to check if curruent// position is valid or notbool 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 elementsvoid 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 Codeint 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 approachimport 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 vectorsdRow = [ -1, 0, 1, 0 ]dCol = [ 0, 1, 0, -1 ] vis = []# Function to check if curruent# position is valid or notdef 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 elementsdef 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 matrixgrid = [ [ 1, 2, 3, 4 ], [ 5, 6, 7, 8 ], [ 9, 10, 11, 12 ], [ 13, 14, 15, 16 ] ]# Row of the matrixM = len(grid)# Column of the matrixN = len(grid[0])DFS_iterative(grid, M, N)# This code is contributed by mukesh07. |
C#
// C# program for the above approachusing 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> |
Output:
1 5 9 13 14 15 16 12 8 7 3 4 11 10 6 2
Time Complexity: O(N*M)
Auxiliary Space: O(N*M)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
