prim算法和kruskal算法的生成树一样吗（prim算法）

你们好，最近小活发现有诸多的小伙伴们对于prim算法和kruskal算法的生成树一样吗，prim算法这个问题都颇为感兴趣的，今天小活为大家梳理了下，一起往下看看吧。

1、最小生成树相关概念：

2、 带权图：边赋以权值的图称为网或带权图，带权图的生成树也是带权的，生成树T各边的权值总和称为该树的权。

3、 最小生成树（MST）：权值最小的生成树。

4、 生成树和最小生成树的应用：要连通n个城市需要n－1条边线路。可以把边上的权值解释为线路的造价。则最小生成树表示使其造价最小的生成树。

5、最小生成树的性质：

6、 MST性质：假设G＝(V,E)是一个连通网，U是顶点V的一个非空子集。若(u,v)是一条具有最小权值的边，其中u∈U，v∈V－U，则必存在一棵包含边(u,v)的最小生成树。

7、

8、构造网的最小生成树必须解决下面两个问题：

9、 （1）尽可能选取权值小的边，但不能构成回路；

10、 （2）选取n－1条恰当的边以连通n个顶点；

以上就是prim算法这篇文章的一些介绍，希望对大家有所帮助。

免责声明：本文由用户上传，如有侵权请联系删除！