This post is completed by 1 user

  • 1
 Add to List
Beginner

445. 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.

  1. Initialize stack.
  2. Initialize 2d boolean array, the same size as the original array. This will help us in avoiding traversal to go in loops.
  3. 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.

Output:

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

Related Problems: