सी ++ प्रोग्राम यह जांचने के लिए कि क्या निर्देशित ग्राफ एक पेड़ है या डीएफएस का उपयोग नहीं कर रहा है

एक ग्राफ एक पेड़ है यदि इसमें कोई चक्र नहीं है। यह एक C++ प्रोग्राम है जो यह जांचने के लिए है कि निर्देशित ग्राफ ट्री है या नहीं DFS का उपयोग कर रहा है।

एल्गोरिदम

Begin
function cyclicUtil() :
   a) Mark the current node as visited and part of recursion stack
   b) Recur for all the vertices adjacent to this vertex.
   c) Remove the vertex from recursion stack.
function cyclic() :
   a) Mark all the vertices as not visited and not part of recursion stack
   b) Call the CyclicUtill() function to detect cycle in different trees
End

उदाहरण

#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class G {
   int n;
   list<int> *adj; //contain adjacent list.
   bool CyclicUtil(int v, bool visited[], bool *rs);
   public:
      G(int V); // Constructor
      void addEd(int v, int w);
      bool cyclic();
};
G::G(int n) {
   this->n = n;
   adj = new list<int> [n];
}
void G::addEd(int v, int u) //to add edges in the graph {
   adj[v].push_back(u); //add u to v’s list
}
bool G::CyclicUtil(int v, bool visited[], bool *recurS) {
   if (visited[v] == false) {
      visited[v] = true; //Mark the current node as visited and part of recursion stack
      recurS[v] = true;
      // Recur for all the vertices adjacent to this vertex.
      list<int>::iterator i;
      for (i = adj[v].begin(); i != adj[v].end(); ++i) {
         if (!visited[*i] && CyclicUtil(*i, visited, recurS))
            return true;
         else if (recurS[*i])
            return true;
      }
   }
   recurS[v] = false; //Remove the vertex from recursion stack.
   return false;
}
//check if the graph is tree or not
bool G::cyclic() {
   //Mark all the vertices as not visited and not part of recursion stack
   bool *visited = new bool[n];
   bool *recurS = new bool[n];
   for (int i = 0; i < n; i++) {
      visited[i] = false;
      recurS[i] = false;
   }
   // Call the CyclicUtill() function to detect cycle in different trees
   for (int i = 0; i < n; i++)
      if (CyclicUtil(i, visited, recurS))
         return true;
         return false;
}
int main() {
   G g(4);
   g.addEd(0, 2);
   g.addEd(1, 2);
   g.addEd(2, 0);
   g.addEd(3, 2);
   if (g.cyclic())
      cout << "Directed Graph isn't a tree";
   else
      cout << "Directed Graph is a tree";
      return 0;
}

आउटपुट

Directed Graph isn't a tree