Data Modelling & AI Data Structure & Algorithm

Breadth First Traversal ( BFS ) on a 2D array

21 June 2025

0

Given a matrix of size M x N consisting of integers, the task is to print the matrix elements using Breadth-First Search traversal.

Examples:

Input: grid[][] = {{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}, {13, 14, 15, 16}}
Output: 1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16

Input: grid[][] = {{-1, 0, 0, 1}, {-1, -1, -2, -1}, {-1, -1, -1, -1}, {0, 0, 0, 0}}
Output: -1 0 -1 0 -1 -1 1 -2 -1 0 -1 -1 0 -1 0 0

Approach: Follow the steps below to solve the problem:

Initialize the direction vectors dRow[] = {-1, 0, 1, 0} and dCol[] = {0, 1, 0, -1} and a queue of pairs to store the indices of matrix cells.
Start BFS traversal from the first cell, i.e. (0, 0), and enqueue the index of this cell into the queue.
Initialize a boolean array to mark the visited cells of the matrix. Mark the cell (0, 0) as visited.
Declare a function isValid() to check if the cell coordinates are valid or not, i.e lies within the boundaries of the given Matrix and are unvisited or not.
Iterate while the queue is not empty and perform the following operations:
- Dequeue the cell present at the front of the queue and print it.
- Move to its adjacent cells that are not visited.
- Mark them visited and enqueue them into the queue.

Note: Direction vectors are used to traverse the adjacent cells of a given cell in a given order. For example (x, y) is a cell whose adjacent cells (x – 1, y), (x, y + 1), (x + 1, y), (x, y – 1) need to be traversed, then it can be done using the direction vectors (-1, 0), (0, 1), (1, 0), (0, -1) in the up, left, down and right order.

Below is the implementation of the above approach:

C++

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
#define ROW 4
#define COL 4
 
// Direction vectors
int dRow[] = { -1, 0, 1, 0 };
int dCol[] = { 0, 1, 0, -1 };
 
// Function to check if a cell
// is be visited or not
bool isValid(bool vis[][COL],
             int row, int col)
{
    // If cell lies out of bounds
    if (row < 0 || col < 0
        || row >= ROW || col >= COL)
        return false;
 
    // If cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise
    return true;
}
 
// Function to perform the BFS traversal
void BFS(int grid[][COL], bool vis[][COL],
         int row, int col)
{
    // Stores indices of the matrix cells
    queue<pair<int, int> > q;
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.push({ row, col });
    vis[row][col] = true;
 
    // Iterate while the queue
    // is not empty
    while (!q.empty()) {
 
        pair<int, int> cell = q.front();
        int x = cell.first;
        int y = cell.second;
 
        cout << grid[x][y] << " ";
 
        q.pop();
 
        // Go to the adjacent cells
        for (int i = 0; i < 4; i++) {
 
            int adjx = x + dRow[i];
            int adjy = y + dCol[i];
 
            if (isValid(vis, adjx, adjy)) {
                q.push({ adjx, adjy });
                vis[adjx][adjy] = true;
            }
        }
    }
}
 
// Driver Code
int main()
{
    // Given input matrix
    int grid[ROW][COL] = { { 1, 2, 3, 4 },
                           { 5, 6, 7, 8 },
                           { 9, 10, 11, 12 },
                           { 13, 14, 15, 16 } };
 
    // Declare the visited array
    bool vis[ROW][COL];
    memset(vis, false, sizeof vis);
 
    BFS(grid, vis, 0, 0);
 
    return 0;
}

Java

// Java program for the above approach
import java.util.*;
 
class GFG{
     
static class pair
{ 
    int first, second; 
     
    public pair(int first, int second)  
    { 
        this.first = first; 
        this.second = second; 
    }    
} 
 
static final int ROW = 4;
static final int COL = 4;
 
// Direction vectors
static int dRow[] = { -1, 0, 1, 0 };
static int dCol[] = { 0, 1, 0, -1 };
 
// Function to check if a cell
// is be visited or not
static boolean isValid(boolean vis[][],
                       int row, int col)
{
     
    // If cell lies out of bounds
    if (row < 0 || col < 0 || 
        row >= ROW || col >= COL)
        return false;
 
    // If cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise
    return true;
}
 
// Function to perform the BFS traversal
static void BFS(int grid[][], boolean vis[][],
                int row, int col)
{
     
    // Stores indices of the matrix cells
    Queue<pair > q = new LinkedList<>();
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.add(new pair(row, col));
    vis[row][col] = true;
 
    // Iterate while the queue
    // is not empty
    while (!q.isEmpty())
    {
        pair cell = q.peek();
        int x = cell.first;
        int y = cell.second;
 
        System.out.print(grid[x][y] + " ");
 
        q.remove();
 
        // Go to the adjacent cells
        for(int i = 0; i < 4; i++) 
        {
            int adjx = x + dRow[i];
            int adjy = y + dCol[i];
 
            if (isValid(vis, adjx, adjy)) 
            {
                q.add(new pair(adjx, adjy));
                vis[adjx][adjy] = true;
            }
        }
    }
}
 
// Driver Code
public static void main(String[] args)
{
     
    // Given input matrix
    int grid[][] = { { 1, 2, 3, 4 },
                     { 5, 6, 7, 8 },
                     { 9, 10, 11, 12 },
                     { 13, 14, 15, 16 } };
 
    // Declare the visited array
    boolean [][]vis = new boolean[ROW][COL];
 
    BFS(grid, vis, 0, 0);
}
}
 
// This code is contributed by 29AjayKumar

Python3

# Python3 program for the above approach
from collections import deque as queue
 
# Direction vectors
dRow = [ -1, 0, 1, 0]
dCol = [ 0, 1, 0, -1]
 
# Function to check if a cell
# is be visited or not
def isValid(vis, row, col):
   
    # If cell lies out of bounds
    if (row < 0 or col < 0 or row >= 4 or col >= 4):
        return False
 
    # If cell is already visited
    if (vis[row][col]):
        return False
 
    # Otherwise
    return True
 
# Function to perform the BFS traversal
def BFS(grid, vis, row, col):
   
    # Stores indices of the matrix cells
    q = queue()
 
    # Mark the starting cell as visited
    # and push it into the queue
    q.append(( row, col ))
    vis[row][col] = True
 
    # Iterate while the queue
    # is not empty
    while (len(q) > 0):
        cell = q.popleft()
        x = cell[0]
        y = cell[1]
        print(grid[x][y], end = " ")
 
        #q.pop()
 
        # Go to the adjacent cells
        for i in range(4):
            adjx = x + dRow[i]
            adjy = y + dCol[i]
            if (isValid(vis, adjx, adjy)):
                q.append((adjx, adjy))
                vis[adjx][adjy] = True
 
# Driver Code
if __name__ == '__main__':
   
    # Given input matrix
    grid= [ [ 1, 2, 3, 4 ],
           [ 5, 6, 7, 8 ],
           [ 9, 10, 11, 12 ],
           [ 13, 14, 15, 16 ] ]
 
    # Declare the visited array
    vis = [[ False for i in range(4)] for i in range(4)]
    # vis, False, sizeof vis)
 
    BFS(grid, vis, 0, 0)
 
# This code is contributed by mohit kumar 29.

C#

// C# program for the above approach
using System;
using System.Collections.Generic;
public class GFG
{
 
  class pair
  { 
    public int first, second; 
 
    public pair(int first, int second)  
    { 
      this.first = first; 
      this.second = second; 
    }    
  } 
  static readonly int ROW = 4;
  static readonly int COL = 4;
 
  // Direction vectors
  static int []dRow = { -1, 0, 1, 0 };
  static int []dCol = { 0, 1, 0, -1 };
 
  // Function to check if a cell
  // is be visited or not
  static bool isValid(bool [,]vis,
                      int row, int col)
  {
 
    // If cell lies out of bounds
    if (row < 0 || col < 0 || 
        row >= ROW || col >= COL)
      return false;
 
    // If cell is already visited
    if (vis[row,col])
      return false;
 
    // Otherwise
    return true;
  }
 
  // Function to perform the BFS traversal
  static void BFS(int [,]grid, bool [,]vis,
                  int row, int col)
  {
 
    // Stores indices of the matrix cells
    Queue<pair> q = new Queue<pair>();
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.Enqueue(new pair(row, col));
    vis[row,col] = true;
 
    // Iterate while the queue
    // is not empty
    while (q.Count!=0)
    {
      pair cell = q.Peek();
      int x = cell.first;
      int y = cell.second;
      Console.Write(grid[x,y] + " ");
      q.Dequeue();
 
      // Go to the adjacent cells
      for(int i = 0; i < 4; i++) 
      {
        int adjx = x + dRow[i];
        int adjy = y + dCol[i];
        if (isValid(vis, adjx, adjy)) 
        {
          q.Enqueue(new pair(adjx, adjy));
          vis[adjx,adjy] = true;
        }
      }
    }
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Given input matrix
    int [,]grid = { { 1, 2, 3, 4 },
                   { 5, 6, 7, 8 },
                   { 9, 10, 11, 12 },
                   { 13, 14, 15, 16 } };
 
    // Declare the visited array
    bool [,]vis = new bool[ROW,COL];
    BFS(grid, vis, 0, 0);
  }
} 
 
// This code is contributed by 29AjayKumar

Javascript

<script>
 
// Javascript program for the above approach
 
var ROW = 4;
var COL = 4;
 
// Direction vectors
var dRow = [-1, 0, 1, 0 ];
var dCol = [0, 1, 0, -1 ];
 
// Function to check if a cell
// is be visited or not
function isValid(vis, row, col)
{
    // If cell lies out of bounds
    if (row < 0 || col < 0
        || row >= ROW || col >= COL)
        return false;
 
    // If cell is already visited
    if (vis[row][col])
        return false;
 
    // Otherwise
    return true;
}
 
// Function to perform the BFS traversal
function BFS( grid, vis,row, col)
{
    // Stores indices of the matrix cells
    var q = [];
 
    // Mark the starting cell as visited
    // and push it into the queue
    q.push([row, col ]);
    vis[row][col] = true;
 
    // Iterate while the queue
    // is not empty
    while (q.length!=0) {
 
        var cell = q[0];
        var x = cell[0];
        var y = cell[1];
 
        document.write( grid[x][y] + " ");
 
        q.shift();
 
        // Go to the adjacent cells
        for (var i = 0; i < 4; i++) {
 
            var adjx = x + dRow[i];
            var adjy = y + dCol[i];
 
            if (isValid(vis, adjx, adjy)) {
                q.push([adjx, adjy ]);
                vis[adjx][adjy] = true;
            }
        }
    }
}
 
// Driver Code
// Given input matrix
var grid = [[1, 2, 3, 4 ],
                       [5, 6, 7, 8 ],
                       [9, 10, 11, 12 ],
                       [13, 14, 15, 16 ] ];
// Declare the visited array
var vis = Array.from(Array(ROW), ()=> Array(COL).fill(false));
BFS(grid, vis, 0, 0);
 
 
</script>

Output:

1 2 5 3 6 9 4 7 10 13 8 11 14 12 15 16

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!

1 COMMENT

Shortest path between two points in a Matrix with at most K obstacles – Neveropen Tech 13 July 2025 At 10:39 pm

[…] The shortest path can be searched using BFS on a Matrix. Initialize a counter vector, this array will keep track of the number of remaining obstacles that […]

Log in to leave a comment

Breadth First Traversal ( BFS ) on a 2D array

C++

Java

Python3

C#

Javascript

LangExtract + Milvus: A Practical Guide to Building a Hybrid Document Processing and Search System

Stop Your AI Assistant from Writing Outdated Code with Milvus SDK Code Helper

A Practical Guide for Choosing the Right Vector Database for Your AI Applications

1 COMMENT

LEAVE A REPLY Cancel reply

Most Popular

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

How to record calls on your Samsung Galaxy phone

How to measure (and understand) your smartphone’s charging speed

EDITOR PICKS

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

How to record calls on your Samsung Galaxy phone

POPULAR POSTS

TCL debuts the first smart TVs with Google Gemini

Android 16 QPR2 Beta 1 introduces ‘expanded’ dark theme settings

How to record calls on your Samsung Galaxy phone

POPULAR CATEGORY

ABOUT US

FOLLOW US