用std::queue实现BFS时，节点入队前必须检查visited标记，否则会导致重复入队、死循环；推荐用std::vector（下标即编号）或std::map记录访问状态，处理非连续编号图需先用std::set收集所有节点ID再BFS。
用 std::queue 实现 BFS 时，节点入队前必须检查是否已访问
不加访问标记直接入队会导致重复访问、死循环甚至栈溢出（对邻接表而言是无限入队）。C++ 中最简方式是用 std::vector 或 std::unordered_set 记录状态，推荐前者——下标即节点编号，O(1) 查找且无哈希开销。
常见错误现象：queue 持续增长、程序卡死、输出路径重复或长度异常。
- 初始化时把起点标记为
true，再入队 - 每次从
queue取出节点后，才遍历其邻接点 - 对每个邻接点
v，仅当!visited[v]时标记并入队
邻接表 vs 邻接矩阵：BFS 的时间与空间取舍
邻接表适合稀疏图（边数 ≪ 节点数²），遍历所有邻接点的总代价是 O(V + E)；邻接矩阵固定查 O(V) 行，BFS 总耗时升为 O(V²)，但实现更直白——尤其适合节点数 ≤ 1000 且需频繁查两点是否连通的场景。
使用场景举例：
- 社交网络好友关系（稀疏）→ 用
std::vector<:vector>>存邻接表 - 网格地图连通性（如 50×50 方格）→ 邻接矩阵或坐标偏移法更易写
- 若需多次 BFS（如多源起点），邻接表复用成本更低
判断图是否连通：一次 BFS 足够，但得确认访问节点数
无向图连通性 = 从任意起点出发 BFS 后，visited 中 true 的个数是否等于总节点数 n。注意：图可能不包含节点 0，或节点编号不连续（如输入含 2、5、7），此时不能只看 visited.size()。
实操建议：
- 读入边时同步记录所有出现过的节点 ID，存入
std::set或排序去重后的std::vector - BFS 前用该集合大小作为预期连通节点数
expected_count - BFS 结束后统计
visited中对应 ID 的true个数，比对即可
漏掉这步，遇到离散编号图会误判为“不连通”。
完整可运行片段：带输入解析的 BFS 连通性检测
以下代码处理无向图，支持非连续编号，使用邻接表 + std::queue，最后输出是否连通及访问顺序：
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
int main() {
int m; std::cin >> m; // 边数
std::set<int> nodes;
std::map<int std::vector>> graph;
for (int i = 0; i > u >> v;
graph[u].push_back(v);
graph[v].push_back(u);
nodes.insert(u); nodes.insert(v);
}
if (nodes.empty()) {
std::cout ids(nodes.begin(), nodes.end());
std::map<int bool> visited;
for (int id : ids) visited[id] = false;
std::queue<int> q;
int start = ids[0];
visited[start] = true;
q.push(start);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : graph[u]) {
if (!visited[v]) {
visited[v] = true;
q.push(v);
}
}
}
int cnt = 0;
for (int id : ids) if (visited[id]) ++cnt;
std::cout <p>关键点：用 <code>std::map<int bool></int></code> 替代数组索引，避免节点编号过大或稀疏导致内存浪费；<code>std::set</code> 自动去重排序，保证 <code>ids</code> 可靠。</p>
<p>真正容易被忽略的是输入阶段——没收集全节点集就直接跑 BFS，哪怕逻辑再正确，连通性判断也一定错。</p></int></int></int></int></algorithm></map></set></vector></queue></iostream>
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
