Depth First Search in C++ After studying from Introduction to Algorithm and taking help from internet I have written a program. I don't know much about C++11. Please help me to optimize this program with better functions and better runtime.

Note: I have used adjacency matrix instead of adjacency list and I don't know whether I have used it in correct way.

#include &lt;iostream&gt;
#include &lt;vector&gt;

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

  struct Vertex
  {
  char id;
  Color color;
  Vertex(char c, Color clr) : id(c), color(clr) {}
  };
  std::vector&lt; std::vector&lt;int&gt; &gt; adjMatrix; //adjacency Matrix
  std::vector&lt;Vertex&gt; vertices;

public:
  Graph(int);
  void addEdge(int, int);
  void DFS(int);
};

Graph::Graph(int v)
{
  V = v;
  adjMatrix.resize(V, std::vector&lt;int&gt;(V));
  for(int i = 0; i &lt; V; i++)
  {
    vertices.push_back( Vertex('A'+i, Color::WHITE));
    for(int j = 0; j &lt; V; j++)
    {
      adjMatrix[i][j] = 0;
    }
   }
}

void Graph::addEdge(int a, int b)
{
  adjMatrix[a][b] = 1;
}

void Graph::DFS(int u)
{
  vertices[u].color = Color::GRAY;
  std::cout &lt;&lt; vertices[u].id &lt;&lt;" ";

  for(int i = u; i &lt; V; i++)
  {
    for(int j = 0; j &lt; V; j++)
    {
      if(adjMatrix[i][j] == 1)
      {
        if(vertices[j].color == Color::WHITE)
        DFS(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.DFS(2);
  return 0;
}
Reduce Complexity, Follow SRP
In both this question and the Binary Search Tree in C++ struct definitions have been embedded within the class definitions. This goes against good object oriented programming principles, specifically the Single Responsibility Principle. One of the basics of object oriented programing is to be able to reuse objects in multiple programs. Each object should be defined separately so that one builds up a library of objects/files that can be reused. In C++ a struct is a class where all members are public, since they are classes they should be defined on their own.

In this program it would be better if there be three header files and possibly two source files, one for Graph and one for Vertex. Vertex may not need a C++ source file since it is fairly simple. The color class also deserves it's own header file. In the Binary Search Tree question Node should be defined separately from BinaryTree.

You might also want to look into SOLID programming principles (the S is the Single Responsibility Principle).

The Single Responsibility Principle states that every module or class should have responsibility over a single part of the functionality provided by the software, and that responsibility should be entirely encapsulated by the class. All its services should be narrowly aligned with that responsibility.


  Robert C. Martin expresses the principle as follows:
          A class should have only one reason to change.


While this is primarily targeted at classes in object oriented languages it applies to functions and subroutines well.

Inconsistent Indentation
The contents of the struct Vertex are not indented and they should be.

Inconsistent Naming Conventions
The naming of variables and functions is inconsistent, there are well named functions and variables such as adjMatrix, addEdge(), id and color, and then there are names such as V and DFS(). It might be better to name V as verticyCount or maxVirtecies and DFS() as depthFirstSearch().

Inconsistent Initialization in Constructors
The constructor for Vertex uses C++ initialization for it's variables, but the Graph constructor does. It might be better if Graph was written as :

Graph::Graph(int v)
: V{v}
{
    adjMatrix.resize(V, std::vector&lt;int&gt;(V));
    for(int i = 0; i &lt; V; i++)
    {
        vertices.push_back( Vertex('A'+i, Color::WHITE));
        for(int j = 0; j &lt; V; j++)
        {
            adjMatrix[i][j] = 0;
        }
    }
}


Please note that the call to std::vector.resize() is not necessary in this constructor. C++ implementations generally include a base allocation of memory for constructors and as the vector grows or shrinks, resize will be called implicitly. Also note that operators such as + should be separated by spaces to make the code more readable.

        vertices.push_back(Vertex('A' + i, Color::WHITE));


In the initialization of Vertex, braces should be preferred to parens:

    Vertex(char c, Color clr) : id{c}, color{clr} {}


The use of parens is supported for backwards compatibility on some C++ compilers, however, it is obsolete.

The two other answers concerns about the DFS() function are valid, you can find a fast working Breath First Search recursive implementation in the KnightMovesImplementation.cpp file, function bool KnightMovesImplementation::CalculatePath(KMMove CurrentMove) in this question.