C++: Depth First Search program using Adjacency Matrix (Graph Algorithm)

Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. [wikipedia]

It explores edges out of the most recently discovered vertex v that still has unexplored edges leaving it. Once all of v's edges have been explored, the search "backtracks" to explore edges leaving the vertex from which v was discovered. This process continues until we have discovered all the vertices that are reachable from the original source vertex. If any undiscovered vertices remain, then depth-first search selects one of them as a new source, and it repeats the search from that source. The algorithm repeats this entire process until it has discovered every vertex. [Introduction to Algorithm(CLSR)]

#include <iostream>
#include <vector>

class Graph
  int vertexCount; //no of Vertices
  enum class Color { WHITE, GRAY, BLACK };

  struct Vertex
  int id;
  Color color;
  Vertex(int vertex, Color clr) : id(vertex), color(clr) {}
  std::vector< std::vector<bool> > adjMatrix; //adjacency Matrix
  std::vector<Vertex> vertices;

  void addEdge(int, int);
  void depthFirstSearch(int);

Graph::Graph(int v)
  vertexCount = v;
  adjMatrix.resize(vertexCount, std::vector<bool>(vertexCount));
  for(int i = 0; i < vertexCount; i++)
    vertices.push_back( Vertex(i, Color::WHITE));
    for(int j = 0; j < vertexCount; j++)
      adjMatrix[i][j] = false;

void Graph::addEdge(int a, int b)
  adjMatrix[a][b] = true;
  adjMatrix[b][a] = true;

void Graph::depthFirstSearch(int u)
  vertices[u].color = Color::GRAY;
  std::cout << vertices[u].id <<" ";

    for(int j = 0; j < vertexCount; j++)
      if(adjMatrix[u][j] == true)
        if(vertices[j].color == Color::WHITE)

  vertices[u].color = Color::BLACK; //blacken u, it is finished

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

  return 0;
You can see this code on GitHub.



You may also like 

C++: Binary Tree using STL 
SPOJ Problem - CPTTRN6 - Character Patterns (Act 6)  
Check if the String is Palindrome (C++ & Java Program)  
C++: Huffman Coding using STL  
C++: Maximum Priority Queue