GESP 八级 · GESP 202406 C++ 八级 第 25 题

要判断无向图的连通性，在深度优先搜索和广度优先搜索中选择，深度优先的平均时间复杂度更低。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

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

【考点】图的遍历算法复杂度｜平均与最坏情况区分｜无向图边计数特性

出品，

1. 🎯 考纲定位

本题出自 GESP 八级「数据结构与算法」模块，核心考点为「图的遍历算法复杂度」。命题人专门在此处设问，意在检验考生对「最坏情况」与「平均情况」的区分——绝大多数考生只记住了 DFS 和 BFS 都是 O(V+E)，却忽略了平均情况下两者完全相等，这正是八级题的典型陷阱。