Breadth-First Search Algorithm For Graphs in C++

In this article, we will learn about the breadth-first search algorithm for graphs. It is one of the most popular graph traversal algorithms. We will start by learning the concept, then writing the pseudocode, and later, conclude this article by coding the algorithm. So without wasting any time, let’s quickly jump to the concept.

What Is Breadth-First Search Algorithm?

The breadth-first search is a very popular graph traversal algorithm. It is also called the Grassfire algorithm because of its evenly spreading nature. In this algorithm, we start by visiting the neighbors in increasing order of distance from the source node. Basically first, we print all the neighbors that have 1 unit distance from the source, then we move to the neighbors that have 2 units distance from the source, and so on for all the remaining nodes.

Now it’s time to look at the pseudocode for the algorithm.

Note: BFS is also known as SSSP(Single Source Shortest Path) algorithm for unweighted and undirected graphs.

Pseudocode for breadth-first search

This pseudocode is nothing but a series of steps that we are going to implement in our code.

We see from the adjacency list what are the neighbours of the source node.
Create a queue that will store the nodes of the graph
Push the source node into the queue
Now push all the neighbours of the source node into the queue.
Pop the source node out of the queue
Now we run a while loop until the queue becomes empty
We also maintain a boolean map that will store the information about the nodes that are already visited.
During each iteration of the while loop we implement the following instructions.
- You mark the node that has been visited once as true in the visited array
- If a node is already visited, we do not insert that node into the queue again
- While inserting the neighbours of a node into the queue, just insert those neighbours that are not already visited.
- Make sure to mark the node as visited as soon as it gets inserted into the queue

For this article, let’s consider the following graph as an example.

Sample Graph

Below is a BFS dry-run example on an example graph.

BFS Traversal Example

Implementing Breadth-First Search Algorithm In C++

To demonstrate this algorithm, we will also need a graph to iterate upon. For this, we will also use a custom graph class in the code below.



#include 

#include 

#include 

#include  using namespace std; template 

class Graph

{ map>> l; // adjacency list

public: void add_edge(T node, T neighbour, int distance = 1, bool is_directed = false) { // is_directed variable is marked as false by default but // if the graph is a directed graph, we will not add the edge // between the neighbour and the node l[node].push_back(make_pair(neighbour, distance)); if(!is_directed) l[neighbour].push_back(make_pair(node, distance)); } void print_graph() { // now we will iterate over all the keys in the map // then we will print the linked list of neighbours // associated with these nodes for(auto p : l) { // iterate over all the neighbours of this particular node T node = p.first; list > neighbour = p.second; cout << "Neighbours of: " << node << " are:

"; for(auto nbr : neighbour) { T dest = nbr.first; int distance = nbr.second; cout << "Neighbour: " << dest << " " << " Distance: "<< distance << endl; } cout << endl; } } void bfs(T src) { // map to mark the nodes as visited map  visited; // queue that will temporarily store the nodes queue  q; // push the source node into the queue and // mark it as visited q.push(src); visited[src] = true; while(!q.empty()) { // extract the front node and print it T node = q.front(); q.pop(); cout << node << endl; for(pair  nbr : l[node]) { // note that nbr is a pair of // the neighbour and its distance // from the source node // check if the neighbour is already visited // or not if(!visited[nbr.first]) { // insert each neighbour into the queue // mark it as visited q.push(nbr.first); visited[nbr.first] = true; } } } return; }

}; int main()

{ Graph  g; g.add_edge("Delhi", "Jaipur"); g.add_edge("Delhi", "Shamli"); g.add_edge("Delhi", "Mumbai"); g.add_edge("Shamli", "Lucknow"); g.add_edge("Shamli", "Baghpat"); g.add_edge("Jaipur", "Bikaner"); g.add_edge("Udaipur", "Jaipur"); g.add_edge("Uttarlai", "Jaipur"); g.add_edge("Jaipur", "Jodhpur"); g.add_edge("Mumbai", "Jaipur"); g.bfs("Delhi"); return 0;

}

BFS Algorithm

Output

BFS Graphs Output

Conclusion

In this article, we learned about the breadth-first search algorithm for graphs. We started by discussing the concept behind BFS(Breadth-First Search), then we moved towards the pseudocode. In the end, we coded a C++ program to demonstrate this algorithm over an example graph. That’s basically it, for now, thanks for reading.