题13

题13

题目

Q:下列关于并查集的叙述中, ( ) 是错误的 (注, 本题涉及图的考点).
A. 并查集是用双亲表示法存储的树
B. 并查集可用于实现克鲁斯卡尔算法
C. 并查集可用于判断无向图的连通性
D. 在长度为 的并查集中进行查找操作的时间复杂度为

分析

A:在用并查集实现 Kruskal 算法求图的最小生成树时: 判断是否加入一条边之前, 先查找这条边关联的两个顶点是否属于同一个集合 (即判断加入这条边之后是否形成回路), 若形成回路, 则继续判断下一条边; 若不形成回路,则将该边和边对应的顶点加入最小生成树 ,并继续判断下一条边,直到所有顶点都已加入最小生成树 。B 正确。
用并查集判断无向图连通性的方法: 遍历无向图的边, 每遍历到一条边, 就把这条边连接的两个顶点合并到同一个集合中, 处理完所有边后, 只要是相互连通的顶点都会被合并到同一个子集合中, 相互不连通的顶点一定在不同的子集合中。 正确。
未做路径优化的并查集在最坏情况下的高度为 ,此时查找操作的时间复杂度为 ,时间复杂度通常指最坏情况下的时间复杂度。D 错误。

解

D