[算法系列之二十七]Kruskal最小生成树算法

红太狼 2023-06-22 11:59 72阅读 0赞

**简介**

求最小生成树一共有两种算法，一个是就是本文所说的Kruskal算法，另一个就是Prime算法。在详细讲解Kruskal最小生成树算法之前，让我们先回顾一下什么是最小生成树。

我们有一个带权值的图，我们要求找到一个所有生成树中具有最小权值的生成树。如下图所示，T是图G的生成树。但不是具有最小权值的生成树。

![20150314160124653][]

我们可以把他们想象成一组岛屿和连接它们的可能的桥梁。当然修桥是非常昂贵和费时的，所以我们必须要知道建设什么样的桥梁去连接各个岛。不过有一个重要的问题，建设这样一组连接所有岛屿的桥梁的最低价格是多少。

![20150314160932985][]

我们实际上需要构建一棵最小生成树，顶点表示岛屿，而边表示它们之间可能要修建的桥梁。每一个可能修建的桥梁都有相应的权值（表示我们建造它所花费的时间和金钱等）。

在实践中，我们只可能使用一个最小生成树的可能用例。（This scenario is only one of possible use cases of where minimum spanning trees can be used in practice.）

**概要**

Kruskal算法开始由初始化一组集合，并建立| V|棵树，每棵树都只包含了图的一个顶点。

![20150314164040865][]

在建设最后生成树的过程中，我们维护一个森林。很显然，我们由|V|棵树组成的森林开始，其中每个树都只有是一个节点。

![20150314164642036][]

在某些时候，我们有“K”棵树组成的森林，这几棵树都最小生成树的子树。

![20150314170630300][]

构建最终的最小生成树最后一个步骤之前，我们有两个树（如上图的3），我们用剩下的最小权值边来连接这两棵树。

构建树的过程中，我们按照权值的升序，对边进行排序。

![20150314171845068][]

然后，获取边，检查每条边（u，v），其端点u和v是否是属于同一棵树。如果是，把（u，v）加入森林中就会形成一个回路，所以放弃这条边（u，v）。否则，说明两个顶点分属不同的树。

![20150314172843696][]

关于Kruskal算法一个很大的特点是，它也可以用在非连同图中。

**原文**

[Computer Algorithms: Kruskal’s Minimum Spanning Tree][Computer Algorithms_ Kruskal_s Minimum Spanning Tree]

本文原文地址：[https://blog.csdn.net/SunnyYoona/article/details/44261291][https_blog.csdn.net_SunnyYoona_article_details_44261291]

[20150314160124653]: https://img-blog.csdn.net/20150314160124653
[20150314160932985]: https://img-blog.csdn.net/20150314160932985
[20150314164040865]: https://img-blog.csdn.net/20150314164040865
[20150314164642036]: https://img-blog.csdn.net/20150314164642036
[20150314170630300]: https://img-blog.csdn.net/20150314170630300
[20150314171845068]: https://img-blog.csdn.net/20150314171845068
[20150314172843696]: https://img-blog.csdn.net/20150314172843696
[Computer Algorithms_ Kruskal_s Minimum Spanning Tree]: http://www.stoimen.com/blog/2012/11/12/computer-algorithms-kruskals-minimum-spanning-tree/
[https_blog.csdn.net_SunnyYoona_article_details_44261291]: https://blog.csdn.net/SunnyYoona/article/details/44261291