# 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> v;
int dist[n];
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++.