判断下列说法是否正确：相比于Kruskal算法，Prim算法

[单选题]

判断下列说法是否正确：相比于Kruskal算法，Prim算法更适合于求边稠密的无向网的最小代价生成树。（）

推荐

白驹之过隙

选A。该题考察的是求最小生成树两种算法的使用场景。

编辑于 2019-10-25 14:28:14 回复(0)

天尊墨宇

选A。该题考察的是求最小生成树两种算法的使用场景。

发表于 2020-06-20 14:11:25 回复(0)

Cola_kkkk

选择A正确，在求最小代价生成树时，kruskal算法利用贪心的算法思想对每个边的权值排序，然后选取最小的边，再看两个节点是否连通，而prim直接在一个集合中选取一个点，然后选择边权值最小的。故在边稠密的无向图中，prim算法更为合适

发表于 2019-10-27 11:00:28 回复(0)

GoAshore

假设网中有n个节点和e条边，普利姆算法的时间复杂度是O(n^2)，克鲁斯卡尔算法的时间复杂度是O(eloge)，可以看出前者与网中的边数无关，而后者相反。因此，普利姆算法适用于边稠密的网络而克鲁斯卡尔算法适用于求解边稀疏的网。

发表于 2022-11-26 19:29:17 回复(0)

提交观点

问题信息

图

上传者：zsw3

难度：

4条回答 208收藏 4446浏览

扫一扫，把题目装进口袋