Search⌘ K
Home
Courses
Competitive Programming - Crack Your Coding Interview, C++

Breadth-First Search - Implementation

Explore how to implement Breadth-First Search (BFS) in C++ using template classes and adjacency lists. Learn to traverse graphs efficiently with BFS by managing visited nodes and queues, including coding and complexity details.

We'll cover the following...

Implementation

Let’s look at the implementation of Breadth-First Search.

C++
#include <iostream>
#include <map>
#include <queue>
#include <list>
using namespace std;
template <typename T>
class Graph
{
  map<T, list<T>> adjList;
  public:
    Graph()
    {
    }
    void addEdge(T u, T v, bool bidir = true)
    {
      adjList[u].push_back(v);
      if (bidir)
        adjList[v].push_back(u);
    }
    void bfs(T source_node)
    {
      queue<T> q;
      map<T, bool> visited;
      q.push(source_node);
      visited[source_node] = true;
      while (!q.empty())
      {
        T node = q.front();
        cout << node << "  ";
        q.pop();
        for (int neighbor : adjList[node])
        {
          if (!visited[neighbor])
          {
            q.push(neighbor);
            visited[neighbor] = true;
          }
        }
      }
    }
};
int main()
{
  Graph<int> g;
  g.addEdge(0, 1);
  g.addEdge(1, 2);
  g.addEdge(0, 4);
  g.addEdge(2, 4);
  g.addEdge(2, 3);
  g.addEdge(3, 5);
  g.addEdge(3, 4);
  g.bfs(0);
}

Explanation:

  • From lines 1 to 4, we import all the header files required.
  • On line 7, we define a template class in C++.

    Templates are powerful features of C++ that allow you to write generic programs. In simple terms, you can create a single function or a class to work with different data types using templates. ...

  • On line 10, we define our adjacency list.
  • On line 12, we define our constructor for the class.
  • On line 15, we define a function addEdge() which will accept the two vertices that need to be joined by an edge and also a boolean value that will determine whether the edge is