c++dfs 输出所有路径
时间: 2024-01-05 13:48:24 浏览: 30
可以使用深度优先搜索(DFS)来输出所有路径。下面是一个简单的 C++ 代码示例:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记每个点是否已经访问过
void dfs(int u, vector<int>& path) {
vis[u] = true; // 标记当前点已经访问过
path.push_back(u); // 将当前点添加到路径中
if (u == n) { // 如果已经到达终点,输出路径
for (int i = 0; i < path.size(); i++) {
cout << path[i] << " ";
}
cout << endl;
} else { // 否则继续搜索
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
dfs(v, path);
}
}
}
vis[u] = false; // 回溯
path.pop_back();
}
int main() {
int m; // 边数
cin >> n >> m;
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u); // 无向图需要添加反向边
}
vector<int> path;
dfs(1, path); // 从起点 1 开始搜索
return 0;
}
```
这个代码使用邻接表表示图,其中 `G[u]` 存储与点 `u` 相邻的所有点,`vis[u]` 表示点 `u` 是否已经访问过,`dfs(u, path)` 表示从点 `u` 开始搜索,当前路径为 `path`。在 `dfs()` 函数中,首先标记当前点已经访问过,并将其添加到路径中。如果已经到达终点,输出路径;否则继续搜索与当前点相邻的所有未访问过的点。最后回溯,将当前点从路径中删除并标记为未访问过。