无向图找环算法给我c++代码
时间: 2023-10-27 07:08:56 浏览: 49
以下是无向图找环的基本算法,使用深度优先搜索(DFS)实现,代码中使用邻接表表示图:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1005;
vector<int> graph[MAXN];
bool visited[MAXN];
bool dfs(int u, int parent) {
visited[u] = true;
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if(!visited[v]) {
if(dfs(v, u)) return true;
} else if(v != parent) {
return true;
}
}
return false;
}
bool hasCycle(int n) {
for(int i = 1; i <= n; i++) {
visited[i] = false;
}
for(int i = 1; i <= n; i++) {
if(!visited[i]) {
if(dfs(i, -1)) return true;
}
}
return false;
}
int main() {
int n, m;
cin >> n >> m;
for(int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
}
if(hasCycle(n)) {
cout << "The graph has a cycle." << endl;
} else {
cout << "The graph doesn't have a cycle." << endl;
}
return 0;
}
```
其中,dfs(u, parent) 函数用于从节点 u 开始进行 DFS,parent 表示 u 的父节点,如果找到了环则返回 true;hasCycle(n) 函数用于检查整个图是否存在环。