克鲁斯卡尔（Kruskal）算法
基本介绍
克鲁斯卡尔算法是用来求加权连通图的最小生成树的算法。
基本思想
按照权值从小到大的顺序选择n-1条边，并保证这n-1条边不构成回路。
首先构造一个只含n个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
问题举例
1、某城市新增7个站点(A, B, C, D, E, F, G) ，现在需要修路把7个站点连通
2、各个站点的距离用边线表示(权) ，比如 A – B 距离 12公里
3、问：如何修路保证各个站点都能连通，并且总的修建公路总里程最短?
过程
1、先把边的按权值进行排序，得[2，3，4
克鲁斯卡尔（Kruskal）算法是一种经典的图论算法，用于寻找加权无向图的最小生成树。最小生成树是指在不增加任何边的权值的情况下，连接图中所有顶点的树形子图，其总权重尽可能小。
算法的基本思路如下：
1. 将图中的所有边按权值从小到大排序。
2. 初始化一个空的边集合，用来存放最终的最小生成树的边。
3. 遍历排序后的边，检查当前边是否与已选择的边形成环路。如果没有形成环路，则将这条边添加到结果集合中。
4. 当添加的边数量达到图的顶点数量减一（即n-1）时，最小生成树构建完成。
以题目中的问题为例，假设某城市有7个站点(A, B, C, D, E, F, G)，需要通过修建道路将它们连通，且权值最小。我们先将所有边按照权值排序，例如：[2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16]。然后依次检查这些边，每次添加一条边前，都要确保添加后不会形成环路。我们可以使用并查集（Disjoint Set）数据结构来快速判断是否构成环路，它能够高效地进行“查找”和“合并”操作。
在Java代码实现中，我们通常创建一个类`Kruskal`，包含边的个数、顶点数组、邻接矩阵等成员变量，以及构造函数、打印方法、排序边的方法和实际执行克鲁斯卡尔算法的方法。在`kruskal()`方法中，我们遍历所有边，使用并查集来判断边是否可以添加，如果可以，就将其加入结果中。当所有边都检查过，最小生成树也就构建完成了。
克鲁斯卡尔算法的优势在于其简单直观，但是缺点是处理环路检测时效率相对较低，特别是对于边数量较多的图。此外，由于依赖于边的排序，对于动态变化的图，克鲁斯卡尔算法可能不如Prim算法灵活。
在实际应用中，克鲁斯卡尔算法常被用于网络设计、资源分配等领域，例如构建成本最低的通信网络、规划最优的交通路线等。理解并掌握这种算法，对于解决实际问题和优化系统性能具有重要意义。
