问kruskal算法的性能如何受到不相交集数据结构的影响？

EN

Kruskal的算法首先对边缘进行排序。这可以在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))加上路径压缩)。

因此，Kruskal的算法具有朴素不相交的数据结构实现：

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))

数据结构“不相交集”对于确保O(E*logE)的总体复杂性是非常重要的。

让我们考虑一下标准的kruskal algo。

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)中使用“不相交集”数据结构来完成。查找和联合部分的总体复杂性是O(E)。

加上O(V) + O(E * logE) + O(E) = O(E * logE)

因此，数据结构“不相交集”对于确保O(E * logE)的总体复杂性是非常重要的。