Breadth First Search using adjacency list I want to improve this code using STL. Let me know if I should add any other function in this code.

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;queue&gt;
#include &lt;list&gt;
#include &lt;limits&gt;

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

  enum { INFINITY = std::numeric_limits&lt;int&gt;::max() };

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

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

public:

  std::vector&lt;Vertex&gt; vertices;
  std::vector&lt; std::list&lt;int&gt; &gt; 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 &lt; 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&lt;Vertex&gt; q;
   q.push(vertices[s]);
   while (!q.empty())
   {
      auto u = q.front();
      q.pop();
      for (auto v = adjList[u.id].begin(); v != adjList[u.id].end(); v++)
      {
         if (vertices[*v].color == WHITE)
         {
            vertices[*v].color = GRAY;
            vertices[*v].distance = u.distance + 1;
            q.push(vertices[*v]);
         }
      }
      u.color = BLACK;
      std::cout &lt;&lt; vertices[u.id].id &lt;&lt; " at level " &lt;&lt; vertices[u.id].distance &lt;&lt;'\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);
}
Will be fixed soon

Advice 1

In BFS, you don't really need colors. (See alternative implementation.)

Advice 2 (Exposing internals)

public:

  std::vector&lt;Vertex&gt; vertices;
  std::vector&lt; std::list&lt;int&gt; &gt; adjList;


I suggest you put the two fields under private:.

Advice 3

Since an undirected graph is a special case of a directed graph (in which each edge \$\{u, v\}\$ can be simulated by two directed arcs \$(u, v), (v, u)\$), I suggest you implement it as a directed graph, but add a method that inserts an undirected edge by two directed arcs.

Advice 4

I would rip off the actual BFS from the Graph. This is, however, a matter of taste.

Advice 5

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


Why not name int v int vertex_count in the first place? Also, I would go for, for example, std::unordered_map&lt;int, list&lt;int&gt;&gt; since it is not restricted to non-negative integers.

Alternative implementation

This is by no means a best possible implementation, but it demonstrates the overall structure I had in mind:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;unordered_map&gt;
#include &lt;unordered_set&gt;
#include &lt;queue&gt;
#include &lt;algorithm&gt;
#include &lt;iterator&gt;

class Graph
{
public:
    void addEdge(int node1, int node2);
    void addArc(int tailNode, int headNode);
    std::unordered_set&lt;int&gt;&amp; getChildNodesOf(int node);

private:
    std::unordered_map&lt;int, std::unordered_set&lt;int&gt;&gt; m_adjacency_list;
};

void Graph::addArc(int tail, int head)
{
    m_adjacency_list[tail].insert(head);
}

void Graph::addEdge(int tail, int head)
{
    // Simulate an undirected edge via two bidirectional arcs:
    addArc(tail, head);
    addArc(head, tail);
}

std::unordered_set&lt;int&gt;&amp; Graph::getChildNodesOf(int node)
{
    return m_adjacency_list[node];
}

std::unordered_map&lt;int, int*&gt;
computeUnweightedShortestPathTree(Graph&amp; graph, int sourceNode)
{
    std::unordered_map&lt;int, int*&gt; parentMap = { { sourceNode, nullptr }};
    std::queue&lt;int&gt; open;
    open.push(sourceNode);

    while (!open.empty())
    {
        int currentNode = open.front();
        open.pop();
        int* parentNode = new int{currentNode};

        for (int childNode : graph.getChildNodesOf(currentNode))
        {
            if (parentMap.find(childNode) == parentMap.end())
            {
                parentMap[childNode] = parentNode;
                open.push(childNode);
            }
        }
    }

    return parentMap;
}

std::vector&lt;int&gt; tracebackPath(int targetNode,
                               std::unordered_map&lt;int, int*&gt;&amp; shortestPathTree)
{
    std::vector&lt;int&gt; path;
    int currentNode = targetNode;
    int* nextNode = shortestPathTree[currentNode];

    while (true) {
        path.push_back(currentNode);
        nextNode = shortestPathTree[currentNode];

        if (nextNode == nullptr)
        {
            break;
        }

        currentNode = *nextNode;
    } 

    std::reverse(path.begin(), path.end());
    return path;
}

int main()
{
    Graph graph;
    graph.addEdge(0, 1);
    graph.addEdge(0, 4);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);

    for (int sourceNode : { 0, 1, 2, 3, 4 })
    {
        std::unordered_map&lt;int, int*&gt; shortestPathTree =
            computeUnweightedShortestPathTree(graph, sourceNode);

        for (int targetNode : { 0, 1, 2, 3, 4 })
        {
            std::cout &lt;&lt; "Shortest path from " &lt;&lt; sourceNode &lt;&lt; " to " &lt;&lt; targetNode &lt;&lt; ": ";
            std::vector&lt;int&gt; path = tracebackPath(targetNode, shortestPathTree);

            std::copy(path.cbegin(),
                      path.cend(),
                      std::ostream_iterator&lt;int&gt;(std::cout, " "));

            std::cout &lt;&lt; "\n";

        }
    }
}