请用C++写出以邻接表存储的图深度优先搜索判断两点间是否有路
时间: 2023-08-01 12:11:08 浏览: 33
以下是使用邻接表存储的无向图深度优先搜索判断两点间是否有路的 C++ 代码:
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义邻接表存储图的结构体
struct Graph {
int V; // 图的顶点数
vector<vector<int>> adj; // 邻接表
// 构造函数
Graph(int V) {
this->V = V;
adj.resize(V);
}
// 添加边
void addEdge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
// 深度优先搜索
bool DFSUtil(int u, int v, vector<bool>& visited) {
visited[u] = true; // 标记当前节点已访问
if (u == v) return true; // 如果找到了目标节点,返回 true
for (int i = 0; i < adj[u].size(); i++) {
int next = adj[u][i];
if (!visited[next]) { // 如果下一个节点未访问过
if (DFSUtil(next, v, visited)) return true; // 递归搜索下一个节点
}
}
return false; // 没有找到目标节点
}
// 判断两点间是否有路
bool isReachable(int u, int v) {
vector<bool> visited(V, false); // 标记每个节点是否被访问过
return DFSUtil(u, v, visited);
}
};
int main() {
// 初始化一个包含 5 个顶点的无向图
Graph g(5);
g.addEdge(0, 1);
g.addEdge(0, 4);
g.addEdge(1, 2);
g.addEdge(1, 3);
g.addEdge(1, 4);
g.addEdge(2, 3);
g.addEdge(3, 4);
// 判断 0 和 3 之间是否有路
if (g.isReachable(0, 3)) {
cout << "There is a path between 0 and 3." << endl;
} else {
cout << "There is no path between 0 and 3." << endl;
}
// 判断 2 和 4 之间是否有路
if (g.isReachable(2, 4)) {
cout << "There is a path between 2 and 4." << endl;
} else {
cout << "There is no path between 2 and 4." << endl;
}
return 0;
}
```
输出结果为:
```
There is a path between 0 and 3.
There is a path between 2 and 4.
```