用c++实现上述过程
时间: 2024-02-12 13:08:06 浏览: 25
以下是使用 C++ 实现邻接表存储的有向图中判断是否存在从顶点 i 到顶点 j 的路径的代码:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
bool bfs(vector<vector<int>>& graph, int start, int end) {
int n = graph.size();
vector<bool> visited(n, false);
queue<int> q{{start}};
while (!q.empty()) {
int cur = q.front(); q.pop();
if (cur == end) return true;
visited[cur] = true;
for (int nei : graph[cur]) {
if (!visited[nei]) q.push(nei);
}
}
return false;
}
int main() {
int n = 5; // 图中有 5 个顶点
vector<vector<int>> graph(n);
graph[0].push_back(1);
graph[1].push_back(2);
graph[2].push_back(3);
graph[3].push_back(4);
graph[4].push_back(1); // 添加边,构建一个环
int start = 0, end = 3;
if (bfs(graph, start, end)) {
cout << "There exists a path from " << start << " to " << end << endl;
} else {
cout << "There does not exist a path from " << start << " to " << end << endl;
}
return 0;
}
```
这段代码中,我们使用了 STL 中的 vector 和 queue 来分别存储邻接表和遍历顶点的队列。初始时,我们将起始顶点 i 加入队列中,并使用一个布尔类型的数组 visited 来记录每个顶点是否被访问过。在遍历邻接表时,如果相邻的顶点未被访问过,则将其加入队列中。如果队列为空,则说明从顶点 i 无法到达顶点 j,算法结束。如果队列中存在顶点 j,则说明从顶点 i 可以到达顶点 j,算法结束。