GESP 八级 · GESP 202312 C++ 八级 第 23 题

判断图是否连通只能用广度优先搜索算法实现。

别被'只能'两个字卡住，图连通性本质是看任意两点是否可达，BFS、DFS、并查集都能搞定，命题人就是拿绝对化表述挖坑。

学生最容易把'BFS求最短路径’和'BFS判连通’混为一谈，以为只有BFS能判连通。其实DFS同样能遍历所有节点，只要遍历完发现访问节点数等于总数，图就连通；并查集还能在O(n+m)级别合并集合，效率更高。命题人故意用'只能'制造绝对化陷阱，诱导只接触过BFS的学生误判，同时混淆了连通性与最短路径的区别。

【考点】图连通性｜搜索算法（BFS/DFS）｜并查集

这道题卡住的是'连通性判断只能用BFS'的刻板印象。图连通性的本质是任意两点间存在路径，而BFS、DFS都是通过遍历顶点来验证这一性质，并查集则通过动态合并集合高效判定连通分量，三者皆可实现连通性测试。命题人故意用'只能'制造绝对化陷阱，诱导只接触过BFS的学生误判，同时混淆了'连通性'与'最短路径'（BFS常用于无权图最短路，但连通性只需可达性）。若题目改为'判断图是否连通可以用任意搜索算法实现'，则A正确；若改为'可以用并查集实现'，也正确。这类题的核心是理解算法适用场景的多样性，而非死记某一种解法。

从命题视角看，GESP八级近年（2023-2026）图形结构题占比极高，其中搜索算法是高频考点。BFS在题库共考过35题，覆盖8个级别，2026年考了7题，2025年6题，2024年8题，2023年5题，说明它确实是命题人钟爱的工具。但并查集虽然只在题库考过3题（2019年），且集中在CSP入门级和提级，命题人偶尔也会用它来考查更高效的连通性判断，尤其是在数据规模较大时。DFS作为搜索算法的另一半，在题库中出现的频率虽不如BFS高，但在连通性判断上完全等价，只是实现细节不同（DFS用栈或递归，BFS用队列）。命题人考这个点，往往是想让学生跳出'BFS=最短路径’的定势，意识到连通性只需'能走到'，不关心'几步'。

思考心法：拿到题先问'连通性需要什么？'——只需要知道所有节点是否在一个集合里。然后看'谁能做到？'——BFS可以，DFS可以，并查集也可以。再看'命题人想考什么？'——如果是单选且说'只能'，那大概率是错的，因为绝对化表述在算法题里99%是陷阱。具体怎么算？如果是BFS，从任意点出发，标记访问，最后看访问数是否等于n；如果是DFS，同理；如果是并查集，初始化每个点自成一集合，遍历所有边合并，最后看集合数是否为1。

避坑：学生最容易错选A，以为'BFS求最短路径’和'BFS判连通’是一回事。其实连通性判断只需可达性，DFS同样有效。另外，有些同学会忽略并查集，觉得它太冷门，但并查集在连通性问题上效率更高，尤其是边数远大于顶点数时。命题人喜欢在'只能'后面藏'也可以'，比如'判断图是否连通只能用BFS'，正确答案就是'错误'，因为DFS和并查集都能实现。刷到类似题先问自己：命题人想考我算法的充分性还是唯一性？如果是唯一性，那多半是错的。

考频与趋势：图形结构在题库共考过213题，覆盖6个级别，2023年32题，2024年61题，2025年56题，2026年40题，说明图形结构是近年考试的重点。BFS在题库共考过35题，覆盖8个级别，2026年考了7题，2025年6题，2024年8题，2023年5题，呈现逐年上升趋势，尤其是2024-2026年，BFS相关题目占比明显增加。并查集虽然只在题库考过3题（2019年），且集中在CSP入门级和提级，但命题人偶尔也会用它来考查更高效的连通性判断，尤其是在数据规模较大时。DFS作为搜索算法的另一半，在题库中出现的频率虽不如BFS高，但在连通性判断上完全等价，只是实现细节不同（DFS用栈或递归，BFS用队列）。

预测：基于给定数据与经验，未来GESP八级图形结构题仍会保持高频，BFS相关题目将继续增加，尤其是结合最短路径、层次遍历等场景。并查集虽然考频低，但命题人可能会在高级别题目中偶尔出现，尤其是考查连通分量、动态合并等场景。DFS相关题目可能会在连通性判断、拓扑排序等场景中出现，但频率可能不如BFS高。暂无足够依据预测具体年份的考频变化，但总体趋势是图形结构题占比持续上升，BFS相关题目将保持较高频率。