Как на производительность алгоритма Крускала влияет несвязанная структура данных набора?

Question

У меня есть общее представление о том, что такое алгоритм Крускала, и вот что я обнаружил:

Этот алгоритм в основном строит минимальное остовное дерево путем объединения нескольких деревьев, и он начинает с сортировки ребер по их весам. Начиная с пустого подграфа, алгоритм сканирует список ребер, добавляя следующее ребро к подграфу, если он не создает цикл.

Где как непересекающееся множество - это структура данных, у которой на самом деле мало способов получить минимальное связующее дерево, используя метод связанных списков или лесных деревьев.

Что я хочу знать, так это то, как непересекающиеся множества влияют на производительность алгоритма Крускала? Любая помощь может быть оценена.

Answer 1

Структура данных "непересекающийся набор" важна для обеспечения общей сложности O(E*logE).

Давайте рассмотрим стандартный алгоритм kruskal.

KRUSKAL(G):

A = ∅
foreach v ∈ G.V:
    MAKE-SET(v)
foreach (u, v) in G.E ordered by weight(u, v), increasing:
   if FIND-SET(u) ≠ FIND-SET(v):
       A = A ∪ {(u, v)}
       UNION(u, v)
return A

Методы FIND-SET() и UNION() идентифицируют наборы (или леса) и объединяют их. Обе эти операции могут быть выполнены в O(1) со структурой данных "несвязный набор". Общая сложность для части FIND и UNION - O (E).

вместе мы имеем O(V) + O(E * logE) + O(E) = O(E * logE)

Следовательно, структура данных "непересекающийся набор" важна для обеспечения общей сложности O(E*logE).

Answer 2

Алгоритм Крускала сначала сортирует ребра. Это можно сделать в O(E*log(E)) = O(E*log(V^2)) = O(E*2*log(V)) = O(E*log(V)) время.

Затем перебирает края и выполняет O(E) несвязанные-заданные операции структуры данных (2 найти и возможно 1 объединение на каждой итерации). Сложность операций зависит от реализации несвязанного множества. Наивная реализация имеет O(V) операция по объединению и O(1) найти операцию. Это ведет к O(E + V^2) время, потому что операция объединения будет выполнена не более V раз, но даже с лесом несвязных множеств с объединением по рангу сложность обеих операций O(log(V)) (может быть O(α(V)) с добавлением пути сжатия).

Таким образом, алгоритм Крускала с наивной реализацией структуры данных с несвязным множеством:
O(E*log(V)) + O(E + V^2) = O(E*log(V) + V^2) (в достаточно редких графиках доминирует второй член)

реализация, которая имеет по крайней мере объединение по рангу:
O(E*log(V)) + O(E*log(V)) = O(E*log(V))