Depth-First Search Examples:

Java
Java
Python
Python
PHP
PHP
C#
C#
C++
C++
TypeScript
TypeScript
▸ Depth-First Search Quick Review

Depth-first Search in C++

#include <list>

// Example class of a graph implementation:
class Graph {
   public:
       Graph(int Size) 
           :Size(Size) {
           adj = new std::list<int>[Size];
       }
       ~Graph()
       {
           delete[] adj;
       }
       std::list<int>* adj;
       int Size;
};


void dfs(Graph & G, const int startVert) {

   bool* visited = new bool[G.Size];
   for(int i = 0; i < G.Size; ++i) {
       visited[i] = false;
   }

   std::list<int> queue;

   // Mark and enqueue our start vert
   visited[startVert] = true;
   queue.push_front(startVert);

   while(!queue.empty()) {
       // Get the next vert
       int v = queue.front();
       queue.pop_front();
       // Explore it:
       std::list<int>::iterator it;
       for(it = G.adj[v].begin(); it != G.adj[v].end(); ++it) {

           if(!visited[*it]) {
               visited[*it] = true;
               queue.push_front(*it);
           }

       }
   }
   delete[] visited;
}

void dfsAux(Graph & G, int v, bool* visited) {
   visited[v] = true;

   std::list<int>::iterator it;
   for(it = G.adj[v].begin(); it != G.adj[v].end(); ++it) {

       if(!visited[*it]) {
           // pre(); something can happen before the visit.
           dfsAux(G, *it, visited);
           // post(); something can happpen after the visit.
       }
   }
}

void dfsRecursive(Graph & G, const int startVert) {
   bool* visited = new bool[G.Size];
   dfsAux(G, startVert, visited);
   delete[] visited;
}

Find any bugs in the code? let us know!