c++程序实现图的广度遍历:对任意给定的图(顶点数和边数自定),建立它的邻接表并输出,然后利用队列的五种基本运算(置空队列、进队、出队、取队头元素、判队空)实现图的广度优先搜索遍历
时间: 2024-02-24 13:58:06 浏览: 71
好的,下面是一个实现该功能的 C++ 程序,其中使用了 STL 中的队列容器来实现队列的五种基本运算:
```c++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void print_adj_list(vector<vector<int>>& adj_list) {
for (int i = 0; i < adj_list.size(); i++) {
cout << i << ": ";
for (int j = 0; j < adj_list[i].size(); j++) {
cout << adj_list[i][j] << " ";
}
cout << endl;
}
}
void bfs(vector<vector<int>>& adj_list, int start) {
queue<int> q; // 创建一个空队列
q.push(start); // 将起始节点加入队列中
vector<bool> visited(adj_list.size(), false); // 创建一个与节点数相同的布尔型数组,用于记录已经访问过的节点
while (!q.empty()) { // 只要队列不为空,就一直循环
int node = q.front(); // 取出队头元素
q.pop(); // 将队头元素出队
if (visited[node]) {
continue; // 如果该节点已经访问过,就跳过它
}
cout << node << " "; // 对当前节点进行处理,这里只是简单地打印出节点编号
visited[node] = true; // 将该节点标记为已访问
for (int i = 0; i < adj_list[node].size(); i++) { // 遍历当前节点的所有邻居节点
int neighbor = adj_list[node][i];
q.push(neighbor); // 将邻居节点加入队列中
}
}
}
int main() {
int V, E;
cin >> V >> E;
vector<vector<int>> adj_list(V); // 创建一个二维数组,表示邻接表
for (int i = 0; i < E; i++) {
int u, v;
cin >> u >> v;
adj_list[u].push_back(v); // 添加一条从 u 到 v 的边
adj_list[v].push_back(u); // 添加一条从 v 到 u 的边(如果该图是无向图的话)
}
print_adj_list(adj_list); // 输出邻接表
bfs(adj_list, 0); // 从节点 0 开始进行广度优先搜索遍历
return 0;
}
```
在这个程序中,`print_adj_list` 函数用于输出邻接表,`bfs` 函数用于进行广度优先搜索遍历。你可以将上面的代码保存为一个文件,比如 `bfs.cpp`,然后用 C++ 编译器编译并运行这个程序,看看它的输出结果。
阅读全文