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

Question

我对什么是 Kruskal 算法有了基本的了解，这就是我的发现:

该算法基本上是通过合并多棵树来构造一棵最小生成树，它首先根据边的权重对边进行排序。该算法从一个空子图开始，扫描边列表，如果不创建循环，则将下一条边添加到子图。

而disjoint set是一种数据结构，实际上很少有方法可以使用链表或森林树方法来推导最小生成树。

我想知道的是，不相交集如何影响Kruskal 算法的性能？任何帮助都将不胜感激。

Answer 1

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 次，但即使是不相交的集森林，union by rank 两个操作的复杂度都是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))