C++: Breadth First Search using Adjacency List

We can write code for Breadth First Search program using Adjacency Matrix

Here we are going to write using adjacency list. In Depth First Search using Adjacency List we have created linked list but here we are going to use std::list which is available in Standard Template Library.


C++ implemantation of BFS using Adjacency List

#include <iostream>
#include <vector>
#include <queue>
#include <list>
#include <limits>

class Graph
{
  int vertex_count;
  enum Color {WHITE, GRAY, BLACK};

  enum { INFINITY = std::numeric_limits<int>::max() };

  struct Vertex
  {
     int id;
     int distance;
     Color color;

     Vertex(int _id) : id(_id),
                       color(Color::WHITE),
                       distance(INFINITY)
                       {}
  };

public:

  std::vector<Vertex> vertices;
  std::vector< std::list<int> > adjList;

  Graph(int);
  void addEdge(int, int);
  void breadthFirstSearch(int);
};

Graph::Graph(int v)
{
   vertex_count = v;
   adjList.resize(vertex_count);
   for (int i = 0; i < vertex_count; i++)
   {
       vertices.push_back( Vertex(i) );
   }
}

void Graph::addEdge(int src, int dest)
{
  //undirected graph
   adjList[src].push_back(dest);
   adjList[dest].push_back(src);
}

void Graph::breadthFirstSearch(int s)
{
   vertices[s].color = GRAY;
   vertices[s].distance = 0;
   std::queue<Vertex> q;
   q.push(vertices[s]);
   while (!q.empty())
   {
      auto u = q.front();
      q.pop();
      for (const auto& v : adjList[u.id])
      {
         if (vertices[v].color == WHITE)
         {
            vertices[v].color = GRAY;
            vertices[v].distance = u.distance + 1;
            q.push(vertices[v]);
         }
      }
      u.color = BLACK;
      std::cout << vertices[u.id].id << " at level " << vertices[u.id].distance <<'\n';
   }
}

int main()
{
   Graph grp(5);
   grp.addEdge(0, 1);
   grp.addEdge(0, 4);
   grp.addEdge(1, 3);
   grp.addEdge(1, 4);
   grp.addEdge(1, 2);
   grp.addEdge(2, 3);
   grp.addEdge(3, 4);
   grp.breadthFirstSearch(2);
}
 
You can find this code on GitHub.


Output:
Breadth First Search

                                                                  
                                                                  
Reference:
 

You may also like 
C++: Add binary numbers 
C++: Remove all adjacent duplicates from String using Stack 
C++: Move all Even numbers before Odd numbers in Singly Linked List 
C++: Merge two sorted Linked List (in-place)  
C++: Split Singly Circular Linked List program  

Comments