Breadth-First Search Algorithm For Graphs in C++

Filed Under: 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.

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.

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

1. We see from the adjacency list what are the neighbours of the source node.
2. Create a queue that will store the nodes of the graph
3. Push the source node into the queue
4. Now push all the neighbours of the source node into the queue.
5. Pop the source node out of the queue
6. Now we run a while loop until the queue becomes empty
7. We also maintain a boolean map that will store the information about the nodes that are already visited.
8. 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

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

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 <iostream>
#include <map>
#include <queue>
#include <list>

using namespace std;

template <typename T>
class Graph
{
map<T, list <pair <T, int>>> 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 <pair <T, int>> neighbour = p.second;

cout << "Neighbours of: " << node << " are:\n";

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 <T, bool> visited;

// queue that will temporarily store the nodes
queue <T> 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 <T, int> 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 <string> g;

g.bfs("Delhi");

return 0;
}
```

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.

References

To read more about graphs and graph traversal algorithms, you can refer to the following websites.

https://en.wikipedia.org/wiki/Graph_traversal

https://www.tutorialspoint.com/graphs-and-its-traversal-algorithms

close
Generic selectors
Exact matches only
Search in title
Search in content