假设用邻接表示法,请设计一个算法求到顶点v的最短路径长度为K的所有顶点C++代码
时间: 2024-05-01 15:23:02 浏览: 92
以下是使用邻接表示法来求到顶点v的最短路径长度为K的所有顶点的C++代码:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> G[MAXN]; // 邻接表存图
int d[MAXN][MAXN]; // 记录每个顶点到其他顶点的最短距离
void bfs(int s, int k) {
queue<int> que;
que.push(s);
d[s][0] = 0;
while (!que.empty()) {
int u = que.front();
que.pop();
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (d[v][0] == -1) { // 没有访问过
d[v][0] = d[u][0] + 1;
que.push(v);
}
for (int j = 0; j < k; j++) {
if (d[v][j+1] == -1) { // 没有访问过
d[v][j+1] = d[u][j];
que.push(v);
}
}
}
}
}
int main() {
int n, m;
cin >> n >> m;
// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
d[i][j] = -1;
}
}
// 建图
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, k;
cin >> s >> k;
bfs(s, k);
// 输出最短距离为k的顶点
for (int i = 0; i < n; i++) {
if (d[i][k] == k) {
cout << i << endl;
}
}
return 0;
}
```
其中,bfs函数表示从顶点s开始,使用BFS算法求到其他顶点的最短距离,并记录每个顶点到其他顶点的最短距离。
主函数中,先读入图的顶点数n和边数m,然后读入每条边的起点和终点,建图。接着读入起点s和最短距离k,调用bfs函数,求到其他顶点的最短距离。最后输出最短距离为k的顶点。
阅读全文