Implementing BFS without using Queue in C++

In this tutorial, we are going to learn how to implement BFS(Breadth-First Search) without using a queue in C++. BFS is an algorithm used for traversing a tree or a graph in a level order manner.

BFS implementation without using Queue

trees chart

Let n be the number of the nodes in the graph.


  1. Create a boolean array of size n to keep track of the visited nodes while traversing the graph. Initialize all the values as false.
  2. Create an array of size n to store the distance of the nodes from the source node. Initialize all the values of the array as infinite.
  3. Create a vector v to store the BFS traversal order. Initially, the vector is empty.
  4. Take the source node and push it into the vector v. Update the distance of the source node as 0 and also mark the source node as visited.
  5. Create a variable p for traversing through the vector and initialize it to 0.
  6. While p is less than the size of the vector v, repeat the following steps:
    a)  Pick the node whose index is p in the vector v and assign it to u.
    b)  Check for the unvisited adjacent nodes of u. If a node is not visited push it into the vector v, update its distance, and mark it as visited. The distance of an unvisited adjacent node of u from the source node is equal to the distance of u plus 1.
    c) Increment p.


#include <bits/stdc++.h>
using namespace std;
void bfs(int n, vector<int> a[], int src, vector<int> &v, int dist[]){
    int i,u;
    bool visit[n];
    for(i = 0;i < n;i++){
        dist[i] = INT_MAX;
        visit[i] = false;
    visit[src] = true;
    dist[src] = 0;
    i = 0;
    while(i < v.size()){
        u = v[i];
        for(int j = 0;j < a[u].size();j++){
            if(visit[a[u][j]] == false){
                visit[a[u][j]] = true;
                dist[a[u][j]] = dist[u]+1;
int main(){
    int n = 6;
    vector<int> adj[n];
    vector<int> v;
    int dist[n];
    cout<<"BFS traversal:"<<endl;
    for(int i = 0;i < v.size();i++){
        cout<<v[i]<<' ';
    cout<<"Distance of each node from source node:"<<endl;
    for(int i = 0;i < n;i++){
        if(dist[i] != INT_MAX)
            cout<<dist[i]<<' ';
            cout<<"INF"<<' ';




BFS traversal:
0 1 2 4 3 
Distance of each node from source node:
0 1 1 3 2 INF


In the above graph, there is no path from the source node to the 5th node. If a node is not reachable from the source node then its distance would remain infinite.


We hope that you have got a clear idea of how to implement BFS without using a queue in C++.

Leave a Reply

Your email address will not be published. Required fields are marked *