C＋图进阶系列之 kruskal和Prim 算法_图向最小生成树的华丽转身

1. 前言

和形状相似，也有差异性。树中添加一条或多条边，可成图。图中减小一条或多条边，可成树。形态的变化由数据之间的逻辑关系决定。

图用来描述数据之间多对多关系。

树用来描述数据之间一对多关系。

思考如下问题？

如果在一座城市城市里铺设一条地铁，要求：

地铁需要通过每一个街区。

线路或造价等最短（少）。

之间的逻辑关系可以用描述。建设地铁，意味着在图中查找一棵，这样才能满足上述要求。

什么是最小生成树？

所谓最小生成村，指从图中找出一棵树，且此树满足如下几个条件：

包含图中的所有顶点。

树中不能有环（每个顶点仅能出现一次）。

树中所有边的权重之和最小。

如果一个算法能同时解决上面的 个问题，则称这种算法为图的最小生树算法。

本文讲解和 `最小树生成算法。

2. 算法

2.1 算法思想

是如何解决最小生成树中的 个问题？

算法集结了 个核心思想：

贪心思想。

并查集思想。

贪心思想保证权重和最小

先把图中的边按由小到大有序排序，这里的贪心指保证每次选择权重最小的边。如果通过每次选择权重最小的边构成的树显然是权重最小的树。

并查集思想保证顶点的唯一性

树的生成是逐步过程。或者说在生成最小树过程中，有一个边界，把图中的所有顶点分成相对 个部分，一个是构成最小生成树的顶点集合，一个是没有加入树的顶点集合，姑且称为其它集合。

如下图所示，刚开始最小生成树集合是空的。

显然，在把图中的顶点加入到最小生成树顶点集合时，是不能把同一个顶点加入 次的。并查集可以做到这点。

Tips：那么，如何保证操作过程中顶点选择的唯一性?

算法使用了并查集思想。如果对并查集不是很了解，可以翻阅我的相关博文。

好！现在演示一下算法的流程。

把图中的按权重由小到大进行有序排列，且把每一个顶点当成一个独立的集合。如下图所示。

贪心思想：选择权重最小的值为的 加入到最小生成树集合中。

并查集思想：刚开始，和 两顶点不在同一集合，和合并。

现在权重为的边有和，选择边。不在最小生成树顶点集合中，可以加入。

再选择。在最小生成树顶点集合中，不在，分属个不同集合，将加入。

权重为的边有 条。选择。如下图，加入最小生成树。

权重为的边不能选择。因为、已经在同一个集合中。选择，加入最小生成树集合中。

继续选择权重值为的边。可以加入最小生成树。之后，因为已经存在于最小生成树中，和 边不能加入集合中。至此，最小生成树已经完成，且最小生成树的权重之和为。

2.1 编码实现

为了让算法具有通用性，下面使用组织代码。程序中有 个核心：

树类。

并查集类。

除此之外，还有辅助类。

2.1.1 树类实现

描述树结构。算法中要用到并查集数据结构，并查集是基于树单位的数据结构。

顶点类： 用来描述树或图的顶点结构。

树类： 提供维护树顶点的函数。

2.2.2 实现算法

本质是使用并查集合并指定边两端的顶点。

测试： 简化了图的描述，直接提供已经排序的信息，测重测试算法设计是否准确。

输出结果：和前文演示结果一致。

3. 算法

算法核心也是贪心思想，算法流程类似于最短路径算法算法。

相比较于，前者基于静态信息（提前对边按权重排序），后者基于动态信息（由优先队列随时调整）。

3.1 算法流程

如查询如下的。

任意选择一顶点，如。然后把与此顶点相邻的边压入到中，优先队列以边的权重为优先。如下图所示。

从优先队列中选择这条边，检查边两端的顶点是否已经被选择，选择顶点。然后把相邻的邻接边压入到优先队列。

从队列中选择边，选择顶点，且把相邻边压入队列。

选择边，选择顶点，且把压入队列。

从队列中选择，选择顶点，且压入边。

选择边，因边两端顶点都已经选择，再选择边，选择顶点，且把压入队列。

最后选择，选择顶点，完成最小生成树。

3.2 编码实现

和和前面的算法一样。

因为需要动态获取边的权重，对升级：

算法类：

测试

输出结果：

4. 总结

和算法同工异曲。都是使用贪心思想，保证在构建最小生成树时，每次获得到的权重都是最小的。区别再于，使用并查集保证顶点唯一性，使用广度优先搜索。