最小生成树kruskal算法 prim算法和kruscal算法的区别？

prim算法和kruscal算法的区别？

Prim算法：

Prim算法将所有顶点分为A和B两部分。A是目标集。该算法可以看作是一个不断地将B中的顶点转移到一个集合的过程。在这个过程中，从B中的每个顶点到树的最短距离是不断更新和排序的。根据贪心思想，将无环最短路径的顶点从B移到a，Prim算法是在加权连通图中寻找最小生成树，即权值最小且连通到所有节点的树。重点放在树上，树没有环。

Prim算法是这样做的：

首先将一个节点作为最小生成树的初始节点，然后迭代求出最小生成树中每个节点的最小权边，并将其加入到最小生成树中。如果连接后生成循环，请跳过此边并选择下一个节点。当所有节点都加入到最小生成树中时，就可以找到连通图中的最小生成树。

2、Kruskal算法：

kruska算法将多个顶点分成N个部分。该算法可以看作是一个连续合并n个部分的过程。在此过程中，根据权值对多条边进行排序，然后根据贪婪思想对权值最短且无循环的顶点进行合并。

Kruskal算法和prim算法的区别在于，Kruskal需要将所有权重边从小到大排序，然后才能找到最小的生成树节点。排序后的加权边依次添加到最小生成树中。如果添加时生成循环，将跳过此边并添加下一条边。当所有节点都加入到最小生成树中时，就会找到最小生成树。

毫无疑问，Kruskal算法比prim算法在效率上更快，因为Kruskal只需要对加权边进行一次排序，而prim算法需要对加权边进行多次排序。尽管prim算法所涉及的加权边可能不能覆盖连通图中的所有边，但随着排序算法效率的提高，Kruskal算法与prim算法的区别将更加明显。

最小生成树kruskal算法 prim和kruskal算法区别 最小代价生成树

版权声明：本文内容由互联网用户自发贡献，本站不承担相关法律责任.如有侵权/违法内容,本站将立刻删除。