Правило взвешенного союза

Может ли кто-нибудь проверить со мной, использую ли я правило прямо на последнем шаге (7)?

ОБНОВИТЬ:

Числа в скобках — количество элементов (вес(?)) каждого набора, участвующего в объединении. Заглавные буквы — это названия наборов.

Как я понимаю: мы используем в качестве нашего ранга количество элементов? Это сбивает с толку, каждый использует разные термины для одного и того же.

У нас есть профсоюзы:

  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)

введите здесь описание изображения


data-structures union-find
person user2692669    schedule 15.02.2014    source источник

Ответы (2)


arrow_upward
1
arrow_downward

Шаг 7 (и другие) выглядит правильно, а шаг 6 — нет.

На шаге 6 4 должно быть корнем, так как это большее дерево.

person Bernhard Barker    schedule 15.02.2014
comment
1+2+3+4=10 и 5+6=11 , разве 6 не должно быть корнем на шаге 6? (причина веса) - person user2692669; 15.02.2014
comment
Я никогда не видел алгоритма объединения-поиска, который использует значения узлов в качестве веса - это тоже не будет иметь большого смысла, поскольку значения узлов на самом деле не соответствуют времени выполнения операций. Обычно используется высота/глубина дерева. - person Bernhard Barker; 15.02.2014
comment
Я обновил свою проблему, как вы указали, теперь я думаю, что это правильно (?). - person user2692669; 15.02.2014
comment
Извините, в задаче есть подвох, который я редактировал. Эти вещи очень сложные! - person user2692669; 16.02.2014

arrow_upward
0
arrow_downward 

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 (Введение в алгоритмы) .

Надеюсь, это поможет вам!

person Aseem Goyal    schedule 15.02.2014