java - Kruskal 算法实现

Question

我找到了一个创建 makes 和 finds 方法的教程

public void makeSet(long data) {
        Node node = new Node();
        node.data = data;
        node.parent = node;
        node.rank = 0;
        map.put(data, node);
    }

private Node findSet(Node node) {
        Node parent = node.parent;
        if (parent == node) {
            return parent;
        }
        node.parent = findSet(node.parent);
        return node.parent;
    }

这是完整 code 的链接到这是 Kruskal Algorithm 的链接

我很困惑为什么他们要返回一个父节点本身而不是不同的节点，以及当等级设置为 0 时实现 Union 时等级用于什么。我已经尝试找到其他 Kruskal 算法代码和解释，但很少有资料涉及实现。

Answer 1

Kruskal 算法的工作原理如下:

1. 将每个节点放在自己的子树中
2. 按权重对边进行排序
3. 找到连接不同子树中两个节点的第一个节点
4. 加入边连接的子树
5. 重复第 3 步和第 4 步，直到没有更多的边可以测试或树完成

在这个特定的实现中，每个节点可以处于两种状态之一:

1. 它是子树的“主”节点(如果 node.parent == 节点)
2. 是一个非主节点，并且有一个链接到同一子树中的另一个节点(如果 node.parent != 节点)

当您测试一条边是否连接两个单独的子树时，您将第一个节点的主节点与第二个节点的主节点进行比较。如果它们相等，则节点在同一子树中，您可以忽略边。

如果第一个节点的主节点不等于第二个节点的主节点，则加入这些子树:将“第二个节点的主节点”的父节点设置为第一个节点的主节点.

当你最终得到一个具有 (node.parent == node) 的主节点时，你就有了一棵完整的树。当然，简单地计算边会更容易，因为您期望一棵树有 N-1 条边。