本文章详细介绍了在C++编程语言中如何实现图的数据结构——邻接表，并深入讲解了基于此数据结构进行广度优先搜索（BFS）的具体方法和算法实例。适合想了解或复习相关知识的读者参考学习。
本段落介绍如何用C++实现图的邻接表存储以及广度优先遍历方法。
示例：创建如下的无向图：
该图包含5个顶点（a, b, c, d, e）及6条边。
输入格式如下所示：
```
5 // 表示有五个顶点
6 // 表示有六条边
abcde // 每个字母代表一个顶点，顺序为：0 a、1 b、2 c、3 d、4 e
// 下面的数字对表示两个顶点之间存在一条无向边：
0 1 // 第零号节点和第一号节点相连，即a与b
0 2 // 第零号节点和第二号节点相连，即a与c
0 3 // 这里原文有误应为2 3（第2个顶点和第3个定点之间有边）
2 4 // 正确表示 c 和 e 的连接
1 4
输入结束
```
实现代码如下：
```cpp
#include
#include
using namespace std;
const int MAX_V = 50; // 假设图中的顶点数量不会超过这个值
struct Edge {
int to;
};
class Graph {
private:
vector adj[MAX_V]; // 邻接表
public:
void addEdge(int from, int to) {
adj[from].push_back((Edge){to});
if (from != to)
adj[to].push_back((Edge){from}); // 因为是无向图，所以需要双向添加边
}
void BFS() {
bool visited[MAX_V] = {}; // 访问标记数组初始化为false
for(int i=0; i q;
q.push(start);
while (!q.empty()) { // 当队列不为空时
int u = q.front();
q.pop();
for (auto& edge : adj[u]) {
if(!visited[edge.to]){
visited[edge.to] = true;
cout << char(a + edge.to); // 打印顶点的字符表示，并标记已访问
q.push(edge.to);
}
}
}
}
};
```
5星
