prim和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算法的区别将更加明显。

图所示是一个无向带权图,请分别按Prim算法和Kruskal算法求最小生成树？

prim算法的基本思想是假设n=（V，e）是一个有n个顶点的连通网络，T=（U，TE）是最小生成树，其中U是T的顶点集，TE是T的边集。（1）初始U={U0}（U0∈V），TE=φ；（2）从U∈U的所有边中选择最小代价边（U0，V0），V∈V-U并合为te，V0并合为U；（3）重复（2）直到U=V，此时te必须包含n-1条边，则t=（V，{te}）是n的最小生成树，Kruskal算法的基本思想是假设n=（V，e）是一个具有n个顶点的连通网络，（1）n个顶点被视为n个集合；（2） 根据从小到大的权重顺序选择边。所选边应满足两个顶点不在同一组顶点中，且该边位于生成树的边集中。同时，合并边的两个顶点集；（3）重复（2），直到所有顶点都在同一个顶点集中。注：1。最小生成树不是唯一的。2图形从最小的节点开始。

prim和kruskal算法图解 prim与kruskal的区别 prim和kruskal算法区别

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