C ++程序检查无向图是否为树或不使用DFS

如果图形不包含任何循环，则它是一棵树。这是一个C ++程序，用于检查无向图是否为树。

算法

Begin
function cyclicUtil() :
   A) Mark the current node as visited.
   B)为与该顶点相邻的所有顶点递归.
   C) If an adjacent is not visited, then recur for that adjacent.
   D)如果访问了相邻节点而不是当前顶点的父节点，则存在一个循环。
End
Begin
function cyclic():
   A) Mark all the vertices as not visited and not part of recursion stack.
   B) Call the recursive function cyclicUtil() to detect cycle in differentDFS trees.
End

示例

#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class G {
   int n;
   list<int> *adj;
   bool CyclicUtil(int v, bool visited[], int par);
   public:
      G(int n); //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
   adj[u].push_back(v);//add v to u’s list
}
//recusive函数使用visited []检测可从顶点v到达的子图中的循环：
bool G::CyclicUtil(int v, bool visited[], int par) {
   visited[v] = true; // Mark the current node as visited
   //为与该顶点相邻的所有顶点递归
   list<int>::iterator i;
   for (i = adj[v].begin(); i != adj[v].end(); ++i) {
      if (!visited[*i]) //If an adjacent is not visited, then recur for that adjacent {
         if (CyclicUtil(*i, visited, v))
            return true;
      }
      //如果访问了相邻节点而不是当前顶点的父节点，则存在一个循环。
         else if (*i != par)
            return true;
   }
   return false;
}
//检查图是否为树形图。
bool G ::cyclic() {
   bool *visited = new bool[n]; // Mark all the vertices as not visited and not part of recursion stack
   for (int i = 0; i < n; i++)
      visited[i] = false;
      // Call the recursive function CyclicUtil() to detect cycle in different DFS trees
      for (int u = 0; u < n; u++)
         if (!visited[u])
            if (CyclicUtil(u, visited, -1))
               return true;
               return false;
}
int main() {
   G g1(4);
   g1.addEd(0, 1);
   g1.addEd(1, 2);
   g1.cyclic() ? cout << "Undirected Graph isn't a tree\n" : cout
   << "Undirected Graph is a tree\n";
   return 0;
}

输出结果

Undirected Graph is a tree