Breadth First Search in C++

Prerequisites : Adjacency List, Queue data structure(FIFO)
Breadth First Search :
Like DFS, BFS is another form of Graph traversal Algorithm. Instead of going deeper and deeper, unlike DFS it goes in breadth first faishon which means that if it is on node u currently, then it first visits all the neighbours of node u and then the same thing happens with each of its neighbours. Lets understand how this algorithm works with the help of an example.

Consider this undirected graph G of 8 vertices and 8 edges and assume a Queue q which is initially empty. Let vertex 1 be our source vertex. So lets push the vertex 1 into the Queue q. Now push all the unvisited neighbouring vertices of 1 into q and pop vertex 1 from q.
Queue q : 2, 3, 4
Now front element of q is 2 so pop out 2 from q and push all the unvisited neighbouring vertices of 2 in the Queue.
Queue q : 3, 4, 5, 6
front element is 3, so pop it out and push all the unvisited neighbouring vertices of 3 in the Queue.
Queue q : 4, 5, 6, 7
Similarly pop 4 out and push all unvisited neighbouring vertices of 4
Queue q : 5, 6, 7, 8
Now every vertex of graph is visited so pop out every element from q until it is not empty.
Applications in competitive coding :

• To test if a graph is Bipartite.
• Minimum Spanning Tree for unweighted graph.
• Single Source shortest path on unweighted graph.
• Path Finding.

Implementation in C++ :
Problem Statement : Given an unweighted graph G and the distance between any 2 directly connected nodes is 1. You are given a source node s and you have to find the distance of all other nodes from s.
Idea : We will apply BFS and we will maintain a distance vector which do 2 things for us. Firstly it stores distance of each node from source node and secondly it would tell us whether a particular node is already visited or not. Keep distance[source] = 0.
When we are looping over the unvisited neighbours of front element of the queue we do just one extra thing i.e.
distance[unvisitedNeighbour(i)] = distance[q.front] + 1.
Rest of the procedure is same, popping out from queue and checking the unvisited neighbours of next element in the queue.
Code for this problem :

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44

#include<bits/stdc++.h> using namespace std; int n; map<int, vector<int> > adjList; // Considering unweighted graph void bfs(int source){ int dist[n+1]; // distance vector memset(dist, -1, sizeof(dist)); // dist[i] = -1; means node i is unvisited queue<int> q; q.push(source); dist[source] = 0; while(!q.empty()){ int u = q.front(); q.pop(); // Removing front element from queue for(int i = 0 ; i < adjList[u].size() ; i ++){ int v = adjList[u][i]; if(dist[v] == -1){ // True if v is not visited earlier q.push(v); dist[v] = dist[u] + 1; } } } printf("Nodes Number | Distance \n"); for(int i = 1 ; i <= n ; i ++){ printf("%d\t\t\t\t|\t\t%d \n", i, dist[i] ); } } int main(){ int edges; // n = number of nodes, edges = Number of edges scanf("%d%d",&n,&edges); for(int i = 0 ; i < edges ; i ++){ int u, v; scanf("%d%d",&u,&v); adjList[u].push_back(v); adjList[v].push_back(u); } int source; scanf("%d",&source); bfs(source); }

Complexity : O(V + E)
where V : Number of vertices and E : Number of Edges.
Thank you for reading this post on BFS.

The End !