Breadth-First Search is a recursive algorithm used to traverse a Graph. The algorithm starts with an arbitrary node(in case of a graph) and traverses all the nodes adjacent to the current node and stores them in a queue.

Since it is a recursive algorithm, it uses visited array of size = no. of nodes in the graph, which checks if we have already visited that particular node of not. It contains the value 0/1 or True/False and prevents the algorithm from falling into an infinite loop.

The graph can be represented as Adjacency List or Adjacency Matrix. Here we have used Adjacency List for implementing a graph.

**Algorithm**

- First, mark all nodes unvisited & start from a given node(or any arbitrary node, if nothing is given) and push it to the queue.
- Remove the element from the queue, mark it visited, print it.
- Visit the adjacent unvisited node of the current node, and push them into the queue.
- Go to step 2, and repeat the step 2-4 until the queue is not empty and all nodes are not visited.
- If all nodes are visited, then stop.

```
int BFS(vector<vector<int> > &graph){
int v = queue.dequeue
if(queue.empty())
return 0;
cout<<v<<" ";
for(int i=0; i<graph[v].size(); i++)
if(visited[graph[v][i]] == 0){
visited[graph[v][i]] = 1;
queue.enqueue(graph[v][i]);
}
}
BFS(graph)
return 0;
}
```

**Implementation of the above algorithm in CPP (Recursive Version)**

#include <bits/stdc++.h> using namespace std; vector<int> visited(10,0); queue<int> que; int add_edge(vector<int> adj_list[], int u, int v){ adj_list[u].push_back(v); adj_list[v].push_back(u); //if it's undirected graph return 0; } int BFS(vector<int> graph[]){ if(que.empty()) return 0; int v = que.front(); que.pop(); cout<<v<<" "; for(int i=0; i<graph[v].size(); i++){ if(visited[graph[v][i]] == 0){ visited[graph[v][i]] = 1; que.push(graph[v][i]); } } BFS(graph); return 0; } int main() { int n = 7; vector<int>adj_list[n]; add_edge(adj_list,1,6); add_edge(adj_list,1,3); add_edge(adj_list,1,4); add_edge(adj_list,3,2); add_edge(adj_list,3,4); add_edge(adj_list,5,2); cout<<"Nodes are visited using BFS in following order: "; que.push(1); visited[1] = 1; BFS(adj_list); cout<<endl; return 0; }

OutputNodes are visited using BFS in the following order: 1 6 3 4 2 5

The time complexity of the above algorithm is O(E+V), where E is total no. of edges and V is total no. of vertices.

**Applications of BFS**

- Shortest Path and Minimum Spanning Tree for unweighted graph
- Crawlers in Search Engines
- Cycle detection in an undirected graph
- Ford–Fulkerson algorithm
- Test if a graph is Bipartite
- Finding all nodes within one connected component