换别的写法,直接给两个点,不用输入几个顶点几条边
时间: 2024-01-23 18:16:26 浏览: 71
在SQL SERVER中查询数据库中第几条至第几条之间的数据SQL语句写法
好的,以下是另一种实现无向图中两点之间所有路径的方法,直接输入两个点坐标,不需要输入顶点和边的个数:
```c++
#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
unordered_map<int, vector<int>> graph; // 存储图的邻接表
unordered_map<int, bool> visited; // 标记数组,用于遍历时记录节点是否已经被访问过
void addEdge(int u, int v) {
graph[u].push_back(v);
graph[v].push_back(u);
}
void dfs(int u, int v, vector<int>& path) {
visited[u] = true; // 标记当前节点已经被访问
path.push_back(u); // 将当前节点加入路径中
if (u == v) { // 如果当前节点已经到达终点v
for (int i = 0; i < path.size(); i++) {
cout << path[i] << " "; // 输出路径
}
cout << endl;
} else {
for (int next : graph[u]) { // 遍历当前节点的所有邻居
if (!visited[next]) { // 如果邻居节点没有被访问过
dfs(next, v, path); // 继续遍历邻居节点
}
}
}
visited[u] = false; // 回溯,将当前节点的标记取消
path.pop_back(); // 回溯,将当前节点从路径中删除
}
int main() {
int u, v;
cin >> u >> v;
addEdge(0, 1);
addEdge(0, 2);
addEdge(1, 2);
addEdge(2, 3);
addEdge(3, 4);
addEdge(2, 4);
addEdge(4, 5);
vector<int> path;
dfs(u, v, path);
return 0;
}
```
以上代码使用了一个无序哈希表来存储图的邻接表,遍历时使用了一个标记数组来记录节点是否已经被访问过,使用vector<int> path来存储当前遍历的路径。在程序开始时,我们需要手动添加边,可以根据自己的需求来修改。在dfs函数中,如果当前节点已经到达终点v,就输出当前路径,否则继续遍历邻居节点,直到遍历完所有路径。
需要注意的是,如果输入的两个点不在同一个连通块上,那么程序将不会输出任何路径。
阅读全文