加权联盟规则

如果我在最后一步（7）中正确使用规则，有人可以与我联系吗？加权联盟规则

UPDATE：

的括号内的数字是元件的数量（重量（）？），每个组参与在本联盟。大写字母是集合的名称。

据我了解：我们用作排名元素的数量？这让人困惑，每个人都在使用不同的术语来表达同样的东西。

我们有联盟：

U（1,2，A）
U（3,4，B）
U（A，B，C）
U（5 ，6，d）
U（7,8，E）
U（d，C，F）
U（E，F，G）

enter image description here

来源

2014-02-15 user2692669

第7步（和其他）看起来是正确的，但第6步没有。

在步骤6中，4应该是根，因为这是更大的树。

来源

2014-02-15 19:22:58 Dukeling

1 + 2 + 3 + 4 = 10和5 + 6 = 11，不应该是步骤6中的根？（重量的原因） – user2692669

我从来没有见过联合发现算法使用节点的值作为权重 - 这也不会产生太大的意义，因为节点的值并不真正对应于操作的运行时间。它通常使用树的高度/深度。 – Dukeling

我按照您的指示更新了我的问题，我认为现在是正确的（？）。 – user2692669

void combine(int x,int y) 
{ 
    int xroot=find(x),yroot=find(y); 
    if(rank[xroot]<rank[yroot]) 
     parent[xroot]=yroot; 
    else if(rank[xroot]>rank[yroot]) 
    parent[yroot]=xroot; 
    else 
    {///rank of both is equal.. 
     parent[yroot]=xroot; 
     rank[xroot]++; 
    } 
}

使用等级，你看size of set，不去总结顶点，所以步骤6是错误的。

但为什么size？
因为如果我们做大一点的根设定小一点的根，我们需要update较少的节点的父母。我想推荐CLRS (Introduction to Algorithms)。

希望它可以帮助你！

来源

2014-02-15 19:29:36

加权联盟规则

回答

相关问题