试题出自试卷《数据结构-图精编练习题》

问题1选项
A.Prim和Kruskal算法的时间效率相同
B.Prim和Kruskal算法都基于贪心算法
C.Prim算法与边数无关，适合求解边稀疏的图
D.Kruskal算法与边数无关，适合求解边稀疏的图

B

【考点】本题考查数据结构--图--最小代价生成树。
【解析】贪心算法是求解图的最小生成树的基础算法，Prim和Kruskal都是基于贪心算法，B正确。Prim不依赖于边，时间复杂度为O(|V|²)，因此适合求解稠密图；Kruskal每次选择最小权值的边加入森林，它依赖于边，时间复杂度为O(|E|log|E|)，适合求解边稀疏的图。选项A、C和D错误。故本题选B。