Java 数据结构 - 克鲁斯卡尔算法

克鲁斯卡尔算法用于寻找最小生成树，它使用贪心策略。该算法将图视为森林，并将每个节点视为一棵独立的树。一棵树只能连接到另一棵树，当且仅当它在所有可用选项中成本最低且不违反 MST 属性时。

为了理解克鲁斯卡尔算法，让我们考虑以下示例 -

步骤 1 - 删除所有环和并行边

从给定的图中删除所有环和并行边。

如果存在并行边，保留关联成本最低的那条边，并删除所有其他边。

步骤 2 - 按权重递增顺序排列所有边

下一步是创建一个边和权重的集合，并按权重（成本）升序排列它们。

步骤 3 - 添加权重最小的边

现在我们开始从权重最小的边开始向图中添加边。在整个过程中，我们将持续检查生成树属性是否保持不变。如果通过添加一条边，生成树属性不成立，那么我们将考虑不将该边包含在图中。

最小成本是 2，涉及的边是 B,D 和 D,T。我们添加它们。添加它们不会违反生成树属性，因此我们继续选择下一条边。

下一个成本是 3，相关的边是 A,C 和 C,D。我们再次添加它们 -

表中的下一个成本是 4，我们观察到添加它将在图中创建一个回路。

我们忽略它。在此过程中，我们将忽略/避免所有创建回路的边。

我们观察到成本为 5 和 6 的边也会创建回路。我们忽略它们并继续。

现在我们只剩下一个节点需要添加。在两个可用的最小成本边 7 和 8 之间，我们将添加成本为 7 的边。

通过添加边 S,A，我们已经包含了图的所有节点，并且现在我们有了最小成本生成树。