克鲁斯卡算法实行

Question

我发现，创造的品牌和方法，找到这样

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！=节点）

在测试的边缘是否连接两个单独的子树，在第一个节点的主比较到第二结点的主。如果它们相等，则节点位于相同的子树中，并且可以忽略边缘。

如果第一个节点的主人不等于第二个节点的主，你加入这些子树：设置父“第2节点的主”第一节点的到的高手。

当您最终得到一个具有（node.parent ==节点）的主节点时，您将拥有一棵完整的树。当然，简单地计算边缘会更容易，因为您期望树的N-1边。