在邻接表类中编码实现一个函数,干函数输出从顶点source出发,经过一条路径长度为M的路径可达的所有顶点的值(M<最长路径长度),假定图为有向无环图且不带权值
时间: 2024-01-22 18:21:00 浏览: 20
假设邻接表类中顶点的值为int类型,可以编写如下代码:
```
void reachableVertices(int source, int M) {
vector<bool> visited(adjList.size(), false); // 标记是否已经访问过
queue<int> q; // 存储待访问的顶点
q.push(source);
visited[source] = true;
int steps = 0; // 记录当前路径长度
while (!q.empty() && steps < M) {
int size = q.size(); // 当前层的顶点数
for (int i = 0; i < size; i++) {
int curr = q.front();
q.pop();
for (int neighbor : adjList[curr]) {
if (!visited[neighbor]) {
q.push(neighbor);
visited[neighbor] = true;
}
}
}
steps++;
}
// 输出所有可达的顶点
cout << "从顶点" << source << "出发,经过一条路径长度为" << M << "的路径可达的所有顶点的值为:";
for (int i = 0; i < adjList.size(); i++) {
if (visited[i]) {
cout << i << " ";
}
}
cout << endl;
}
```
该函数使用了BFS算法,从源顶点开始,一层一层地遍历图,直到路径长度为M或者所有可达的顶点都被访问过。最后输出所有可达的顶点的值。