Learn Graph Algorithms in C++/

...

/

Implementation of BFS

Implementation of BFS

Learn how to implement Breadth-first Search.

We'll cover the following...

In this lesson, we will implement Breadth-first Search to solve the shortest path problem for unweighted graphs.

Implementation Notes

When implementing DFS previously, we wanted to explore the deepest unexplored node first. This corresponds to using a stack for the unexplored nodes, which is a Last-In-First-Out (LIFO) data structure. Uusually the stack is implicit in the recursive implementation.

For implementing BFS, we want to do the opposite and explore the closest unexplored node first. Hence, we’ll use a queue to store the unexplored nodes, which is a First-In-First-Out (FIFO) data structure.

%0 node_1 u_1 (front) node_2 u_2 node_1->node_2 node_3 u_3 (back) node_2->node_3
The queue of unexplored nodes

The illustration above shows what the queue of unexplored nodes can look. When new vertices are discovered, they’ll be pushed to the back of the queue. However, when we select the next node to explore, we’ll bring it from the front of the queue.

Implementing shortest paths using BFS

We’ll implement a class for the shortest path computation to keep track of the state of the search as we did for BFS. For each node, we’ll store”

  • its distance to the starting vertex.
  • the parent vertex from which we discovered the node.

Again, we’re using the adjacency list representation, which is preferable for graph traversals.

Press + to interact
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
// shorthand for adjacency list type
typedef vector<vector<int>> AdjacencyList;
class ShortestPaths {
private:
    AdjacencyList adjacencyList;
    vector<int> distances;
    vector<int> parents;
    // undiscovered nodes will have -1 as distance / parent
    static constexpr int UNKNOWN = -1;
public:
    ShortestPaths(AdjacencyList &_adjacencyList) 
        : adjacencyList {_adjacencyList}  
        , distances {vector<int>(_adjacencyList.size(), UNKNOWN)}
        , parents {vector<int>(_adjacencyList.size(), UNKNOWN)}
    {}
}

We are using two vector<int> variables, parents and distances, to keep track of the BFS state. Initially, they are both filled with the value -1, which means “yet unknown.”

Unlike in our DFS implementation, we do not explicitly keep track of which nodes are unvisited, in progress, or finished, because we do not want to classify edges. Still, the nodes with a parent of -1 ...