需要对Kruskals和Union-Find做一些澄清

Question

请帮助我填补我的知识空白(自学)：

到目前为止，我了解到，给定一个N个顶点的图，我们想要形成一个具有N-1边的MST。

1. 我们根据边缘的重量来订购。
2. 我们创建了一组子集，其中每个顶点都有自己的子集。因此，如果我们有{A，B，C，D}作为我们的初始顶点集，我们现在有{A}，{B}，{C}，{D}
3. 我们还创建了一个集合A，它将保存答案
4. 我们沿着有序边的列表走下去。我们看它的顶点，所以V1和V2。如果它们在单独的子集中，我们可以将这两个子集连接起来，并将边添加到保持我们的边的集合A中。如果它们在同一个子集中，我们将转到下一个选项(因为它是一个循环)。
5. 我们继续这种模式，直到我们到达边缘列表的末尾，或者我们到达顶点的数目--1表示我们集合A的长度。

如果上述断言是正确的，那么我的以下问题涉及到实现：

如果我们使用list[]来保存包含该顶点的集合的子集：

子集= [1357]

每个边都需要寻找两个子集，所以我们需要找到(6,7)

结果将是

my_path = (6,7) #保存所有路径子集= [135]

在子集中找到子集所花费的时间不会太长而不是O(nlog(n))

有更好的方法吗?还是我做得对？

Answer 1

在子集中找到子集所花费的时间不会太长而不是O(nlog(n))

是

有更好的方法吗?还是我做得对？

更好的方法是采用不相交集林数据结构结合Union的秩技术。应用此技术，对于Union或Find操作，最坏的运行时间为O(log )。

Answer 2

实际上，算法的运行时间是O(E log(V))。

其性能的关键在于您的第4点，更确切地说，是确定轻边e= (a，b)是否'a‘和'b’属于同一集合的实现，如果不是，则执行各自集合的合并。

关于这个主题的更多澄清，我推荐你这本书：“Algoritms简介”，来自麻省理工学院出版社，ISBN 0-262-03293-7，pag 561 (MST的一般主题)和pag 568 (Kruskal的算法)。正如它所述，我引述如下：

图G= (V，E)的Kruskal算法的运行时间取决于不相交集数据结构的实现。我们将假定第21.3节的不相交集-林实现与逐秩合并和路径压缩启发式算法相结合，因为它是已知的渐近最快的实现。

用一些简单的“时间复杂性理论”演算，证明了它的时间复杂度为O(E log(V))。