# 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:**

- Create a boolean array of size
**n**to keep track of the visited nodes while traversing the graph. Initialize all the values as false. - 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. - Create a vector
**v**to store the BFS traversal order. Initially, the vector is empty. - 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. - Create a variable
**p**for traversing through the vector and initialize it to 0. - 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++.

## Leave a Reply