假设一个无向图采用邻接表G作为存储结构,设计一个算法在存在经过顶点v的回路时输出所有这样的简单回路。写出c++代码
时间: 2024-12-12 22:23:05 浏览: 14
为了找到所有包含指定顶点v的简单回路,你可以使用深度优先搜索(DFS)算法,并记录下路径上已经访问过的节点。当发现回路时,停止搜索并反向回溯找出所有的简单路径。以下是C++代码实现:
```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <unordered_set>
using namespace std;
// 辅助函数用于检查是否在路径上
bool inPath(vector<int>& path, int u) {
return find(path.begin(), path.end(), u) != path.end();
}
void dfs(int u, int v, vector<int>& path, vector<vector<int>>& G, unordered_set<int>& visited, vector<vector<int>>& result) {
path.push_back(u);
visited.insert(u);
if (u == v && !inPath(result.back(), u)) { // 如果找到简单回路
result.push_back(path);
return;
}
for (int neighbor : G[u]) {
if (!visited.count(neighbor)) {
dfs(neighbor, v, path, G, visited, result);
} else if (neighbor != v && inPath(path, neighbor)) { // 如果邻居已经在路径上并且不是目标v,说明有交叉回路,跳过
continue;
}
}
path.pop_back(); // 出栈当前节点,继续探索下一个未访问的节点
}
// 主函数
void findAllSimplePathsThroughV(const vector<vector<int>>& G, int v, vector<vector<int>>& result) {
unordered_set<int> visited;
dfs(v, v, {}, G, visited, result); // 首先从v开始搜索
}
int main() {
vector<vector<int>> G = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1}}; // 示例无向图
int v = 2; // 指定顶点
vector<vector<int>> paths;
findAllSimplePathsThroughV(G, v, paths);
if (paths.empty()) {
cout << "No simple cycles found through vertex " << v << endl;
} else {
cout << "Simple cycles through vertex " << v << ": " << endl;
for (const auto& path : paths) {
cout << "[ ";
for (int node : path) {
cout << node << " ";
}
cout << "]" << endl;
}
}
return 0;
}
```
这个代码会输出所有通过顶点v的简单回路,如果没有,则会告知没有简单回路。注意,这个解决方案只适用于寻找简单回路,如果允许复杂的环形结构,结果将包含更长的回路。
阅读全文