今天主要是针对最小生成树的两种算法。
用题目来举例
53. 寻宝（第七期模拟笔试） (kamacoder.com)
题目描述
在世界的某个区域，有一些分散的神秘岛屿，每个岛屿上都有一种珍稀的资源或者宝藏。国王打算在这些岛屿上建公路，方便运输。
不同岛屿之间，路途距离不同，国王希望你可以规划建公路的方案，如何可以以最短的总公路距离将 所有岛屿联通起来（注意：这是一个无向图）。
给定一张地图，其中包括了所有的岛屿，以及它们之间的距离。以最小化公路建设长度，确保可以链接到所有岛屿。
输入描述
第一行包含两个整数V 和 E，V代表顶点数，E代表边数 。顶点编号是从1到V。例如：V=2，一个有两个顶点，分别是1和2。
接下来共有 E 行，每行三个整数 v1，v2 和 val，v1 和 v2 为边的起点和终点，val代表边的权值。
输出描述
输出联通所有岛屿的最小路径总距离
输入示例
输出示例
提示信息
数据范围：
2 <= V <= 10000;
1 <= E <= 100000;
0 <= val <= 10000;
如下图，可见将所有的顶点都访问一遍，总距离最低是6.
题目分析：
实际上就是寻找最小连通子图，以最小的成本（边的权值）将图中所有节点链接到一起。
那么，对于n个结点，就需要n-1条边来将他们连起来。所以我们就需要在所有的边里面选出n-1条边。来看看两种算法怎么选出这些边。
prim算法呢，主要维护的结点的信息，他的思路类似于贪心的策略，每次选代价最小的结点加入到最小生成树中，所以prim算法的三个步骤就是
1.寻找离最小生成树最近的结点
2.将最近结点加入最小生成树
3.更新结点离最小生成树最近的距离
所以我们用一个数组minDist来记录每一个结点距离最小生成树的距离，初始为结点数加1即可。为了方便和结点对应，这个数组我们也开始从1开始使用。
所以他的初始状态为
那么开始构造最小生成树，这边直接选取第一个结点加入最小生成树就好了
1、prim三部曲，第一步：选距离生成树最近节点
选择距离最小生成树最近的节点，加入到最小生成树，刚开始还没有最小生成树，所以随便选一个节点加入就好（因为每一个节点一定会在最小生成树里，所以随便选一个就好），那我们选择节点1 （符合遍历数组的习惯，第一个遍历的也是节点1）
2、prim三部曲，第二步：最近节点加入生成树
此时 节点1 已经算最小生成树的节点。
3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
接下来，我们要更新所有节点距离最小生成树的距离，如图：
注意下标0，我们就不管它了，下标 1 与节点 1 对应，这样可以避免大家把节点搞混。
此时所有非生成树的节点距离 最小生成树（节点1）的距离都已经跟新了 。
- 节点2 与 节点1 的距离为1，比原先的 距离值10001小，所以更新minDist[2]。
- 节点3 和 节点1 的距离为1，比原先的 距离值10001小，所以更新minDist[3]。
- 节点5 和 节点1 的距离为2，比原先的 距离值10001小，所以更新minDist[5]。
注意图中我标记了 minDist数组里更新的权值，是哪两个节点之间的权值，例如 minDist[2] =1 ，这个 1 是 节点1 与 节点2 之间的连线，清楚这一点对最后我们记录 最小生成树的权值总和很重要。
1、prim三部曲，第一步：选距离生成树最近节点
选取一个距离 最小生成树（节点1） 最近的非生成树里的节点，节点2，3，5 距离 最小生成树（节点1） 最近，选节点 2（其实选 节点3或者节点2都可以，距离一样的）加入最小生成树。
2、prim三部曲，第二步：最近节点加入生成树
此时 节点1 和 节点2，已经算最小生成树的节点。
3、prim三部曲，第三步：更新非生成树节点到生成树的距离（即更新minDist数组）
接下来，我们要更新节点距离最小生成树的距离，如图：
此时所有非生成树的节点距离 最小生成树（节点1、节点2）的距离都已经跟新了 。
- 节点3 和 节点2 的距离为2，和原先的距离值1 小，所以不用更新。
- 节点4 和 节点2 的距离为2，比原先的距离值10001小，所以更新minDist[4]。
- 节点5 和 节点2 的距离为10001（不连接），所以不用更新。
- 节点6 和 节点2 的距离为1，比原先的距离值10001小，所以更新minDist[6]。
剩下的步骤就是重复这个过程，我这里就不写了
看看具体的代码实现
不同于prim算法的处理结点，kruskal选择处理的是边，
来看看它的具体思路
krusal的思路：
- 边的权值排序，因为要优先选最小的边加入到生成树里
- 遍历排序后的边
- 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
- 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
可以看到，krusal 算法主要在于判断两个点是否在同一个集合中（最小生成树）,这一部分，就需要用到并查集了，
看看图解
将图中的边按照权值有小到大排序，这样从贪心的角度来说，优先选 权值小的边加入到 最小生成树中。
排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]
(1,2) 表示节点1 与 节点2 之间的边。权值相同的边，先后顺序无所谓。
开始从头遍历排序后的边。
选边(1,2)，节点1 和 节点2 不在同一个集合，所以生成树可以添加边(1,2)，并将 节点1，节点2 放在同一个集合。
选边(4,5)，节点4 和 节点 5 不在同一个集合，生成树可以添加边(4,5) ，并将节点4，节点5 放到同一个集合。
继续这个思路，就可以把所有的点都加到最小生成树中了，看看具体的代码实现
所以，总的来看，最小生成树的两种算法各有各的侧重，那么对于一些边少节点多的情况我们使用Krusal算法，反之Prim算法即可。
对于更详细的解析与其他语言的代码块，可以去代码随想录上查看。