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