Depth-First Search (DFS) in 2D Matrix/2D-Array – Recursive Solution

Objective: Given a two-dimensional array or matrix, Do the depth-First Search (DFS) to print the elements of the given matrix. Implement the Depth-first traversal in a recursive manner.

Example:

int [][] grid = new int[][] {
                  {1, 2, 3, 4},
                  {5, 6, 7, 8},
                  {9, 10, 11, 12},
                  {13, 14, 15, 16}}
Output:
Depth-First Traversal:
1 5 9 13 14 10 6 2 3 7 11 15 16 12 8 4 

Approach – Use Recursion

As we know stack is used for DFS.

  • Initialize stack.
  • Initialize 2d boolean array, the same size as the original array. This will help us in avoiding traversal to go in loops.
  • Make a call to recursive function DFSUtil with row=0, column =0 and visited[] array.

In DFSutil Function

check if row and column indexes are within the range of given matrix and marked false in the visited[] array, if not then return from the function. If indexes are valid and not visited then print the element. Mark the element in the visited array. Make a recursive call to left(column-1), right(column+1), down(row+1) and up(row+1) from the current element position. 

See the code below for more understanding.

Complete Code:

Output:

Depth-First Traversal:
1 5 9 13 14 10 6 2 3 7 11 15 16 12 8 4

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: