Как можно применить структуры данных Union / Find к алгоритму Крускала?

Question

http://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

Объединение / Поиск структуры данных, используемой для непересекающихся множеств...

Answer 1

Это указано в записи для алгоритма Крускала, но вы можете использовать структуру объединения / поиска, чтобы проверить (через FIND ), соединяет ли ребро два разных дерева или образует ли оно цикл при добавлении.

Та же структура может быть обновлена (через ОБЪЕДИНЕНИЕ), если ребро не образует цикл и добавляется в связующее дерево.