algorithm - 使用数组而不是 Kruskals 算法的不相交集来加快合并和查找时间

Question

所以刚刚了解了 Kruskals 的最小生成树算法。所以这是我的理解:

它初始化一个包含所有顶点 V 的不相交集数据结构。

在 |E|log|E| 中按权重对边进行排序后时间或|E|时间使用计数排序(如果权重允许)，Kruskals 算法迭代排序的边，如果节点 u 和 v 不属于不相交集合中的同一集合，则将边 (u,v) 添加到最小生成树structure.Wikipedia 说这个不相交集结构中的查找和搜索时间是 a(V)，其中 a 是阿克曼函数的倒数。

我觉得可以加快查找速度，但不能 100% 确定复杂性。这是我的建议:

对于图中的每个顶点，为其分配一个从 0 到 |V|-1 的值，这些数字现在是它们的索引。初始化一个大小为 |V| 的数组所有值都设置为 0。

当遍历我们的边 (u,v) 时，我们可以在 O(1) 时间内在数组中查找它们的索引，如果这些数组值中的任何一个为 0 则我们将它们都设置为 1 并将这条边添加到我们的最小生成树。

感觉就像这样做，我们可以用 O(V) 时间比 O(a(V)) 更好地查找和合并 Kruskals 算法中的集合，代价是 |V|空间，因为我们需要为每个顶点存储一个额外的值。

这看起来是对的还是我只是对数组访问时间产生了错觉？

Answer 1

您的算法对于 A--1--B--3--C--2--D 失败(字母是顶点，数字是权重)。

但是请注意，您可以仅使用一个数组来实现一个完整的不相交集数据结构，而且实际上经常这样做。我使用这样的表示:

• 每个顶点在数组中都有一个索引(就像你的一样)
• 将所有数组元素初始化为-1。数组值 < 0 表示一个集合的根，其值的否定给出了它的大小或等级。所有顶点都以它们自己的大小为 1 的集合开始。
• 如果数组值 >=0，则表示一个集合链接到该索引处的父集合。合并两个集合时，将较小集合的值设置为较大集合的索引，并在必要时调整较大集合的大小。覆盖较小集合的大小并不重要。它永远不会是根，所以您再也不需要这个尺寸了。