This post is completed by 1 user

  • 1
 Add to List
Beginner

432. Breadth-First Search (BFS) in 2D Matrix/2D-Array

Objective: Given a two-dimensional array or matrix, Do the breadth-First Search (BFS) to print the elements of the given matrix. Implement a Breadth-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:
Breadth-First Traversal:
1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16

Approach - Use Queue

As we know queue is used for BFS.

  1. Initialize queue.
  2. Initialize 2d boolean array, the same size as the original array. This will help us in avoiding traversal to go in loops.
  3. Add the first element position (element at (0,0), row=0, column=0) to queue
  4. Now until the queue is not empty
    1. Take out the position from the queue. 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 get the next position from the queue. 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 queue.
  5. See the code below for more understanding.

Output:

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

Related Problems: