请用c++,写一段代码,实现无向图,两点之间所有的路径
时间: 2024-03-16 22:43:35 浏览: 175
好的,以下是使用C++实现无向图,并输出两点之间所有路径的代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100;
int n, m; // n个点,m条边
vector<int> g[MAXN]; // 存储图的邻接表
int vis[MAXN]; // 标记数组,用于遍历时记录节点是否已经被访问过
void dfs(int u, int v, vector<int>& path) {
if (u == v) { // 如果当前节点已经到达终点v
for (int i = 0; i < path.size(); i++) {
cout << path[i] << " "; // 输出路径
}
cout << endl;
return;
}
vis[u] = 1; // 标记当前节点已经被访问
path.push_back(u); // 将当前节点加入路径中
for (int i = 0; i < g[u].size(); i++) {
int next = g[u][i]; // 遍历当前节点的所有邻居
if (!vis[next]) { // 如果邻居节点没有被访问过
dfs(next, v, path); // 继续遍历邻居节点
}
}
vis[u] = 0; // 回溯,将当前节点的标记取消
path.pop_back(); // 回溯,将当前节点从路径中删除
}
int main() {
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);
}
int s, t;
cin >> s >> t;
vector<int> path;
dfs(s, t, path); // 遍历s到t所有路径
return 0;
}
```
以上代码使用深度优先搜索(DFS)遍历无向图,并输出两点之间所有路径。在DFS遍历过程中,使用标记数组vis记录节点是否已经被访问过,使用vector<int> path记录当前遍历的路径,遍历到终点时,输出当前路径即可。
阅读全文