最小生成树的两种算法?

发布网友发布时间：2022-05-02 04:01

共3个回答

热心网友时间：2022-06-28 00:27

主要有两个：
1.普里姆（Prim)算法
特点：时间复杂度为O(n2).适合于求边稠密的最小生成树。
2.克鲁斯卡尔（Kruskal)算法
特点：时间复杂度为O(eloge)(e为网中边数），适合于求稀疏的网的最小生成树。

热心网友时间：2022-06-28 00:28

Prim算法和 Kruskal算法

Prim算法逐次将最小权的边和相应顶点加到集合中，适合于求边稠密的最小生成树；Kruskal算法先将所有边都放入集合，然后再逐个选择最小权的边，适合于求稀疏的网的最小生成树。

详细过程请参考相关资料

热心网友时间：2022-06-28 00:28

Prim算法
Kruskal算法

声明：本网页内容为用户发布，旨在传播知识，不代表本网认同其观点，若有侵权等问题请及时与本网联系，我们将在第一时间删除处理。E-MAIL:11247931@qq.com