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

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

Algorithm:

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.

Implementation:

#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;
    }
    v.push_back(src);
    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;
                v.push_back(a[u][j]);
            }
        }
        i++;
    }
    
}
int main(){
    int n = 6;
    vector<int> adj[n];
    vector<int> v;
    int dist[n];
    adj[0].push_back(1);
    adj[0].push_back(2);
    adj[2].push_back(1);
    adj[2].push_back(4);
    adj[3].push_back(1);
    adj[4].push_back(3); 
    bfs(n,adj,0,v,dist);
    cout<<"BFS traversal:"<<endl;
    for(int i = 0;i < v.size();i++){
        cout<<v[i]<<' ';
    }
    cout<<endl;
    cout<<"Distance of each node from source node:"<<endl;
    for(int i = 0;i < n;i++){
        if(dist[i] != INT_MAX)
            cout<<dist[i]<<' ';
        else
            cout<<"INF"<<' ';
    }
    cout<<endl;

}

 

Output:

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