GESP 七级 · GESP 202512 C++ 七级 第 22 题

使用邻接矩阵存储一个有 $ V $ 个顶点、$ E $ 条边的图，对该图进行一次完整的 BFS 遍历，时间复杂度为 $ O(V + E) $。

邻接矩阵是n×n的方阵，matrix[i][j]表示顶点i到j是否有边（有权图存权值）。n个顶点需n²空间。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】图的邻接矩阵存储｜BFS遍历｜时间复杂度分析

🎯 考纲定位 本题位于 GESP 七级《数据结构》模块，核心考查图存储结构对算法效率的影响。命题人专门把这道题放在这里，就是要卡住那些只背结论不区分存储结构的考生——他们死记"BFS 是 O(V+E)"，却忘了这个结论只适用于邻接表。

🧠 解题思维 看题先锁定存储方式：邻接矩阵是 V×V 的二维数组，访问顶点 u 的所有邻接点必须扫描整行。BFS 需要访问所有顶点（V 次），每次扫描邻接点又需要 O(V) 时间，总开销 O(V²)。题目给的 O(V+E) 只有在邻接表存储下才成立——邻接表只对存在的 E 条边做遍历。存储结构不同，时间复杂度公式完全不同，这是 BFS 在图结构里的铁律。

🪤 陷阱拆解 A 选项是典型"条件缺失陷阱"：命题人利用考生对 BFS 时间复杂度的机械记忆，故意不写明存储结构，诱导你套用 O(V+E) 这个"标准答案"。真实场景里，邻接矩阵只能用于稠密图（E 接近 V²），邻接表才适合稀疏图；若强行用矩阵存稀疏图，空间浪费巨大，时间也被锁死在 O(V²)，E 再大也没用。记住：BFS 的时间复杂度永远和图的存储方式绑定，脱离存储谈复杂度就是耍流氓。

🔄 反命题思维 命题人视角：如果把"邻接矩阵"改成"邻接表"，答案立刻翻转成 A；如果改成"邻接多重表"，复杂度公式还要变。刷到类似题先问自己：这道题到底在考存储结构、算法本身、还是两者结合？别被"完整 BFS 遍历"这种漂亮词儿带偏，GESP 出题人最喜欢在存储结构上埋雷。