This post is completed by 1 user

  • 0
 Add to List
Beginner

433. Depth-First Search (DFS) in 2D Matrix/2D-Array - Iterative 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 an iterative 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 Stack

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. Push the first element position (element at (0,0), row=0, column=0) to stack
  4. Now until the stack is not empty
    1. pop the position from the stack. Split it by "," to get the row index and column index. and check if indexes are within the range of given matrix and marked false in the visited[] array, if not then ignore it and pop the next position from the stack. If indexes are valid and not visited then print the element.
    2. Mark the element in the visited array.
    3. Add the element positions from left, right, down and up from the current element into the stack.
  5. 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: