普里姆（Prim）算法和克鲁斯卡尔（KrusKal）算法构造最小生成树有什么区别？

红太狼 2021-11-11 06:50 476阅读 0赞

# Prim算法和KrusKal算法构造最小生成树 #

## 前言 ##

先说好，大家一定要耐心看下去，看完了就知道有什么区别了！

**首先，大家回忆一下什么是最小生成树？**

> 最小生成树：就是一个图的生成树集合当中权值之和最小的生成树，可以有一种，也可以有多种，这与图本身结构有关（等会会说到这一点）。

**有的同学就问道，那么什么是生成树？**

> 生成树：就是一个连通图的极小连通子图（它包含图中的所有顶点，并且只含有尽可能少的边。），这意味着对于生成树来说，若看去他的一条边，则会使该生成树（极小连通子图）变为非连通图；同样，你多添加一条边，则图中肯定会形成一条回路。

说到这里，应该都明白什么是生成树了。

回到最小生成树：为什么一个图的最小生成树可能不唯一？

**1. 首先说一下最小生成树唯一的情况！！！**

道理很简单，你要去好几家亲戚家拜年

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70][]

通过选择最短的路程，之前你已经走过了上图中箭头所示的路径到达了爷爷家；

现在从爷爷家去哥哥家有很多种选择，可以走7公里的，走10公里的，甚至还可以绕回来到弟弟家，然后走6公里的（当然“**一般人”**不会这么选择吧），因此根据最小生成树的选法，选择权值最小的边（这里是路程最短的路——7公里），这样一来，整个图的最小生成树就如下图所示。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 1][]

**2. 再说一下最小生成树不唯一的情况！！！**

还是刚才的例子，这回路径变了，如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 2][]

情况和上面的一直，但是这次爷爷去哥哥家的路变成了两条都是10公里的路，那么问题来了选择谁呢？

当然还是根据最小生成树的概念选择一条权值最小的边（这里两条都是10，既然最终路程都是一致，那么就是可以两条任意选择一条即可），得到的最小生成树自然就有两种不同的啦。如下图：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 3][]![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 4][]

？？？说好的讨论普里姆（Prim）算法和克鲁斯卡尔（KrusKal）算法构造最小生成树有什么区别的呢？

哈哈，其实我说这么多就是为了证明一件事。（下面可能说的比较粗鲁）

**普里姆（Prim）算法和克鲁斯卡尔（KrusKal）算法构造最小生成树相不相同，和这两种算法有设么必然的联系吗**

我（一个连通图），能生成最小生成树的个数，不是看我本身有多大能耐吗？管这两位算法小兄弟啥事啊！

连通图才是主角。

说正经的！

一个图的最小生成树是不是唯一的，还得看连通图中的各边权值是不是互不相等；

> 1.  如果互不相等，那么连通图G的生成树肯定是唯一的；而且如果无向连通图的边数比顶点数少1（此时G本身是一棵树），此时G的最小生成树就是它本身。
> 2.  最小生成树的边的权值之和总是唯一的，虽然最小生成树可能不唯一（就是图形不一致），但其对应的变得权值之和总是唯一的，而且是最小的。
> 3.  另外，有个很重要的结论：**最小生成树的边数为顶点数减1。**

我可能有些地方说的不是特别清楚，萌新总结一下自己的想法。

如果有什么不妥的地方，还希望大家指点，谢谢各位了。

日常鸡汤：今天不努力，明天不努力，那么你的人生永远只是在重复。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70]: /images/20211109/3ca829750b3f4d469fb77c48e31f41a6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 1]: /images/20211109/05e17aa6f934436d910a154ab5388fa8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 2]: /images/20211109/0966a8c429444c0ab6631a6b71a12876.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20190804201935408.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM3MzQ0MTI1_size_16_color_FFFFFF_t_70 4]: /images/20211109/905bf78651ba4609a14f43c729c36473.png