C++中图的邻接表存储与广度优先遍历示例解析

简介：
本文章详细介绍了在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); } } } } }; ```