1

我找到了一个创建制作和查找方法的教程

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;
    }

这里是完整代码的链接 这里是Kruskal 算法的链接

我很困惑为什么他们要返回一个其父节点本身而不是不同节点的节点，以及在等级设置为 0 时实施联合时等级的用途。我尝试查找其他 Kruskal 算法代码和解释，但是很少有关于实施的资料。

4

1 回答 1

0

Kruskal 的算法是这样工作的：

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

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

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

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

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

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

于 2017-07-06T15:23:40.613 回答