广度优先搜索从起始节点开始逐层遍历，使用队列实现并用布尔数组标记访问状态，避免重复访问。示例代码展示了无向图的邻接表表示及BFS遍历过程，输出结果为0 1 2 3 4 5；通过记录队列大小可分层输出，应用于最短路径、连通性等问题，时间与空间复杂度均为O(V + E)。
广度优先搜索（Breadth-First Search, BFS）是一种用于遍历或搜索图或树的算法。它从起始节点开始，先访问其所有邻接节点，再逐层向外扩展，直到遍历完所有可达节点。BFS通常使用队列（queue）来实现，保证按层次顺序访问节点。
图的表示方式
在C++中，图常用邻接表表示，可以用vector>存储。例如，graph[u] 存储节点 u 所有直接连接的节点。
示例：无向图的邻接表表示
vector<vector> graph = { {1, 2}, // 节点0连接1和2 {0, 3, 4}, // 节点1连接0、3、4 {0, 5}, // 节点2连接0、5 {1}, // 节点3连接1 {1}, // 节点4连接1 {2} // 节点5连接2};
BFS基本实现步骤
BFS的核心是使用队列维护待访问节点，并用布尔数组记录已访问状态，避免重复访问。
立即学习“C++免费学习笔记（深入）”；
实现要点：
使用queue保存待处理节点使用vector标记是否访问过从起点入队，循环出队并处理其邻居未访问的邻居入队并标记
C++代码实现
#include #include #include using namespace std;void bfs(const vector<vector>& graph, int start) { int n = graph.size(); vector visited(n, false); // 标记访问状态 queue q; q.push(start); visited[start] = true; while (!q.empty()) { int u = q.front(); q.pop(); cout << u << " "; // 输出当前节点 // 遍历u的所有邻接节点 for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } }}// 示例调用int main() { vector<vector> graph = {{1,2}, {0,3,4}, {0,5}, {1}, {1}, {2}}; cout << "BFS traversal: "; bfs(graph, 0); return 0;}
输出结果：
0 1 2 3 4 5
带层级信息的BFS
有时需要知道每个节点所在的层次（距离起点的步数），可以在遍历时记录层数。
修改版：输出每层节点
void bfsWithLevel(const vector<vector>& graph, int start) { int n = graph.size(); vector visited(n, false); queue q; q.push(start); visited[start] = true; int level = 0; while (!q.empty()) { int size = q.size(); // 当前层的节点数 cout << "Level " << level << ": "; while (size--) { int u = q.front(); q.pop(); cout << u << " "; for (int v : graph[u]) { if (!visited[v]) { visited[v] = true; q.push(v); } } } cout << endl; level++; }}
输出示例：
Level 0: 0 Level 1: 1 2 Level 2: 3 4 5
应用场景与注意事项
BFS常用于求解最短路径（无权图）、连通分量、拓扑排序等问题。
常见用途：
计算两个节点间的最短路径（边权为1）判断图是否连通解决迷宫最短路径问题社交网络中查找好友关系层数
注意点：
确保图不为空，起始节点有效无向图需防止来回访问（靠visited数组控制）有向图同样适用，只需按邻接表方向遍历空间复杂度O(V + E)，时间复杂度O(V + E)
基本上就这些。掌握队列的使用和访问标记是关键。
以上就是C++怎么实现广度优先搜索(BFS)_C++图的遍历与队列应用的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1485506.html
微信扫一扫 
支付宝扫一扫 
