找出基环树的环c++ 使用vector存图
时间: 2023-11-04 10:58:26 浏览: 46
要找出基环树的环c,可以使用深度优先搜索(DFS)算法来实现。以下是使用vector存储图的一个示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
vector<bool> visited; // 记录节点是否已经访问过
vector<int> parent; // 记录每个节点的父节点
vector<bool> inCycle; // 记录节点是否在环中
vector<int> cycle; // 存储找到的环
// 深度优先搜索
bool dfs(vector<vector<int>>& graph, int node, int parentNode) {
visited[node] = true;
parent[node] = parentNode;
for (int neighbor : graph[node]) {
if (!visited[neighbor]) {
if (dfs(graph, neighbor, node))
return true;
} else if (neighbor != parentNode) {
// 找到了环
cycle.push_back(neighbor);
inCycle[neighbor] = true;
int cur = node;
while (cur != neighbor) {
cycle.push_back(cur);
inCycle[cur] = true;
cur = parent[cur];
}
cycle.push_back(neighbor); // 将最后一个节点加入环中
return true;
}
}
return false;
}
// 找到基环树的环c
vector<int> findCycle(vector<vector<int>>& graph) {
int n = graph.size();
visited.resize(n, false);
parent.resize(n, -1);
inCycle.resize(n, false);
for (int i = 0; i < n; i++) {
if (!visited[i] && dfs(graph, i, -1))
break;
}
return cycle;
}
int main() {
int n = 4; // 图的节点数
vector<vector<int>> graph(n);
// 添加图的边
graph[0].push_back(1);
graph[1].push_back(0);
graph[1].push_back(2);
graph[2].push_back(1);
graph[2].push_back(3);
graph[3].push_back(2);
vector<int> cycle = findCycle(graph);
// 输出环c中的节点
cout << "环c中的节点: ";
for (int node : cycle) {
cout << node << " ";
}
cout << endl;
return 0;
}
```
以上代码通过深度优先搜索遍历图,当遇到一个已经访问过的节点时,如果该节点不是当前节点的父节点,则找到了一个环。然后通过记录每个节点的父节点,可以回溯找到构成该环的所有节点。