Breadth First Search Algorithm for Graph Traversal (Recursive & Iterative approach)

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

1. First, mark all nodes unvisited & start from a given node(or any arbitrary node, if nothing is given) and push it to the queue.
2. Remove the element from the queue, mark it visited, print it.
3. Visit the adjacent unvisited node of the current node, and push them into the queue.
4. Go to step 2, and repeat the step 2-4 until the queue is not empty and all nodes are not visited.
5. 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;
}

Output

Nodes 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

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