BFS Implementation in C++

What is Breadth First Search(BFS)?

BFS is a graph traversal method that traverses the graph iterative way level by level. That means it traverses the graph “breadth first”, starting from the source then the neighbor of the source then the next level and so on.

For example:

If we traverse the given graph above, the output will be: ‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘K’, ‘I’, ‘J’

‘A’ will be visited first as it is the source node. Then ‘B’, ‘C’, and ‘D’ is in the next level, so they will be visited. And it is the same way the rest of the nodes will be visited.

Implementation of BFS

We will make a class called graph and take a map that has char type as key and vector of char as value. Usually, we take a vector of vector to store values of the nodes but in this graph, as we are storing char values, the index will be char type that is why we have to take map or unordered_map. And we will declare a method to add the edges and a method to do breadth-first search.

Add Edge to the Graph

To add edges we have already declared a method. Now, let's implement the method.

The first two parameters of the method are the two nodes between which we want to add an edge and the third parameter is a boolean to know if the…