3

最後の手順 (7) でルールを正しく使用しているかどうかを誰かに確認してもらえますか?

アップデート：

括弧内の数字は、Union に参加する各セットの要素数 (重み (?)) です。大文字はセットの名前です。

私が理解しているように、要素の数をランクとして使用していますか? これは紛らわしくなっており、それぞれが同じものに対して異なる用語を使用しています。

組合があります：

  1. U(1,2,A)
  2. U(3,4,B)
  3. U(A,B,C)
  4. U(5,6,D)
  5. U(7,8,E)
  6. U(D,C,F)
  7. U(E,F,G)

ここに画像の説明を入力

4

2 に答える 2

1

ステップ 7 (およびその他) は正しいように見えますが、ステップ 6 は正しくありません。

ステップ 6 では、4 がルートである必要があります。これは、より大きなツリーです。

于 2014-02-15T19:22:58.513 に答える
0 
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-15T19:29:36.853 に答える