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;

public:
  Graph(int);
  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)
        depthFirstSearch(j);
      }
    }

  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);

  grp.depthFirstSearch(2);
  return 0;
}
 
You can see this code on GitHub.


                                                                  
                                                                  
Reference

 

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  

Comments