Chương trình C ++ để kiểm tra xem Đồ thị được hướng dẫn là Cây hay Không sử dụng DFS

Một đồ thị là một cây nếu nó không chứa bất kỳ chu trình nào. Đây là một chương trình C ++ để kiểm tra xem một đồ thị có hướng là cây hay không bằng cách sử dụng DFS.

Thuật toán

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

Ví dụ

#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;
}

Đầu ra

Directed Graph isn't a tree