C++ breadth-first search using adjacency matrix

Question

I have written this Breadth First Search program using Adjacency Matrix, taking help from Introduction to Algorithm(CLSR) and from Internet.

I want to optimise this code.

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

class Graph
{
  int vertexCount;
  //WHITE means Undiscovered, GRAY means Discovered, BLACK menas Processed
  enum class Color{ WHITE, GRAY, BLACK };

  const int imax = std::numeric_limits<int>::max();

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

    Vertex(const int vertex, Color clr, int imax) : id(vertex),
                                                    color(clr),
                                                    distance(imax)
                                                    {};
  };
  std::vector< std::vector<bool> > adjMatrix; //adjacency adjMatrix
  std::vector<Vertex> vertices;
public:
    Graph(int size)
  {
    vertexCount = size;
    adjMatrix.resize(vertexCount, std::vector<bool>(vertexCount));
    for(int i = 0; i < vertexCount; i++)
    {
      vertices.push_back( Vertex(i, Color::WHITE, imax));
      for(int j = 0; j < vertexCount; j++)
        adjMatrix[i][j] = false;
    }
  }
    ~Graph() {};

    void BFS(const int);
    void addEdge(int, int);
    void printPath(const int,  const int) const;

};

void Graph::BFS(const int src)
{
    const auto s = vertices[src].id;
    vertices[s].color = Color::GRAY;
    vertices[s].distance = 0;


    std::queue<int> Q;
    Q.push(vertices[s].id);

    while(!Q.empty())
    {
        auto u = Q.front();
        Q.pop();

        for (int j = 0; j < vertexCount; j++)
        {
            if(vertices[j].color == Color::WHITE && adjMatrix[u][j] == true)
            {
                vertices[j].color = Color::GRAY;
                vertices[j].distance = vertices[u].distance + 1;
                Q.push(j);
            }
        }
        vertices[u].color = Color::BLACK;
    }
}

void Graph::addEdge(int u, int v)
{
    adjMatrix[u][v] = true;
  adjMatrix[v][u] = true;
}

void Graph::printPath(const int src, const int ver) const
{
    auto s = vertices[src].id;
    auto v = vertices[ver].id;

  std::cout << s;
  for(int j = s + 1; j <= v; j++)
  {
    if(adjMatrix[s][j] == true)
    {
      std::cout << " --> "<< j;
      s = j;
    }
  }
}

int main()
{
    Graph grp1(8);
    grp1.addEdge(0, 1);
  grp1.addEdge(0, 2);
  grp1.addEdge(1, 3);
  grp1.addEdge(1, 4);
  grp1.addEdge(2, 5);
  grp1.addEdge(3, 4);
  grp1.addEdge(3, 6);
  grp1.addEdge(4, 6);
  grp1.addEdge(4, 7);
  grp1.addEdge(6, 7);

    grp1.BFS(0);
    grp1.printPath(1, 7);
}

Answer 1

A bug

The path printed by main (1, 3, 4, 6, 7) is not shortest. The culprit is the printPath: it needs to know, for each node \$u\$ the value \$u.\text{parent}\$ from which we entered \$u\$. Needless to say, you have never computed it, and printPath computes some path.

Advice 1

struct Vertex is unnecessary since your nodes are represented via simple int values.

Advice 2

You compute the shortest path distances to each node from the source node, but you never use them; you could remove that functionality.

Advice 3

You don't need the colors either. Actually, you don't need in particular the black color. You can simulate whether the node is white or gray via simple inclusion of the node (effectively an int value) to an unordered_set.

Advice 4

adjMatrix is not the best possible name. Some C++ projects prepend each class member field with m_. A better name (in my opinion) would be a verbose m_adjacency_matrix.

Advice 5

I recommend you do not use adjacency matrices for sparse graphs; you will likely waste a hell lot of space. Use adjacency lists instead.

Advice 6

Also, I would remove the printPath from Graph and implement it as a simple function.

Alternative implementation

Below is the way I would go about reimplementing your program. I don't claim it to be too good C++, but that's a start:

#include <algorithm>
#include <iostream>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

class Graph
{
    std::vector<std::unordered_set<int>> m_adjacency_list;

public:
    Graph(int size) : m_adjacency_list(size) {}

    std::unordered_map<int, int> BFS(const int);
    void addEdge(const int, const int);
};

std::vector<int> traceback_path(int source,
                                int target,
                                std::unordered_map<int, int>&& parent_map)
{
    std::vector<int> path;
    int current_node = target;

    while (true)
    {
        path.push_back(current_node);

        if (current_node == source)
        {
            break;
        }

        current_node = parent_map[current_node];
    }

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

std::unordered_map<int, int> Graph::BFS(const int source)
{
    std::unordered_map<int, int> parent_map;
    std::unordered_set<int> closed;
    std::queue<int> frontier;

    parent_map[source] = 0;
    frontier.push(source);

    while (!frontier.empty())
    {
        int current_node = frontier.front();
        frontier.pop();

        for (const int neighbor : m_adjacency_list[current_node])
        {
            if (closed.find(neighbor) == closed.cend())
            {
                closed.insert(neighbor);
                parent_map[neighbor] = current_node;
                frontier.push(neighbor);
            }
        }
    }

    return parent_map;
}

void Graph::addEdge(int u, int v)
{
    // Undirected graph:
    m_adjacency_list[u].insert(v);
    m_adjacency_list[v].insert(u);
}

int main()
{
    Graph grp1(8);
    grp1.addEdge(0, 1);
    grp1.addEdge(0, 2);
    grp1.addEdge(1, 3);
    grp1.addEdge(1, 4);
    grp1.addEdge(2, 5);
    grp1.addEdge(3, 4);
    grp1.addEdge(3, 6);
    grp1.addEdge(4, 6);
    grp1.addEdge(4, 7);
    grp1.addEdge(6, 7);

    std::unordered_map<int, int> parent_map = grp1.BFS(0);
    std::vector<int> path = traceback_path(1, 7, std::move(parent_map));

    for (int node : path)
    {
        std::cout << node << "\n";
    }
}