学习动机

Kruskal 使用并查集结构来保存不断扩展的已选边森林。为了安全地添加一条边，它会检查两个端点是否已经属于同一个集合（这会形成一个环）。

为什么要学习 Kruskal？

• 实际的最小生成树：以最低成本进行网络设计、聚类，以及铺设电缆或道路。
• 并查集：一种优雅、可复用的数据结构，用于跟踪连通性，在计算机科学的许多领域都能见到。
• 贪心算法的正确性：这是另一个例子，说明始终选择成本最低的安全选项可以得到全局最优解。

图的所有最小生成树都使用相同的边权重多重集，因此总权重（以及最大边权重）是唯一的。