运行 Kruskal 算法的时间

Question

Kruskal 算法如下：

MST-KRUSKAL(G,w)
1. A={}
2. for each vertex v∈ G.V
3.      MAKE-SET(v)
4. sort the edges of G.E into nondecreasing order by weight w
5. for each edge (u,v) ∈ G.E, taken in nondecreasing order by weight w
6.      if FIND-SET(u)!=FIND-SET(v)   
7.         A=A U {(u,v)}  
8.         Union(u,v)
9. return A

根据我的课本：

Initializing the set A in line 1 takes O(1) time, and the time to sort the edges in line 4 is O(E lgE). The for loop of lines 5-8 performs O(E) FIND-SET and UNION operations on the disjoint-set forest. Along with the |V| MAKE-SET operations, these take a total of O((V+E)α(V)) time, where α is a very slowly growing function. Because we assume that G is connected, we have |E| <= |V|-1, and so the disjoint-set operations take O(E α(V)) time. Moreover, since α(V)=O(lgV)=O(lgE), the total running time of Kruskal's algorithm is O(E lgE). Observing that |E|<|V|^2, we have lg |E|=O(lgV), and so we can restate the running time of Kruskal's algorithm as O(E lgV).

你能解释一下为什么我们推断第 4 行中对边进行排序的时间是 O(E lgE) 吗？另外我们如何得到总时间复杂度为 O((V+E)α(V)) ？

另外，假设图中所有边的权值都是1到|V|之间的整数。您可以使 Kruskal 算法的速度达到多快运行？对于某个常量 W，如果边权重是 1 到 W 范围内的整数怎么办？

时间复杂度如何取决于边的权重？

编辑：

In addition, suppose that all edge weights in a graph are integers from 1 to |V|. How fast can you make Kruskal's algorithm run?

我有以下想法：

为了使 Kruskal 算法运行更快，我们可以使用计数排序对边进行排序。

第 1 行需要 O(1) 时间。
第 2-3 行需要 O(v) 时间。
第 4 行需要 O(|V|+|E|) 时间。
第 5-8 行需要 O(|E|α(|V|)) 时间。
第 9 行需要 O(1) 时间。

所以如果我们使用计数排序来解决边缘问题，Kruskal 的时间复杂度将是

你能告诉我我的想法是否正确吗？

还有：

What if the edges weights are integers in the range from 1 to W for some constant W?

我们将再次使用计数排序。算法将是相同的。我们发现时间复杂度如下：

第 1 行需要 O(1) 时间。
第 2-3 行需要 O(|V|) 时间。
第4行需要O(W+|E|)=O(W)+O(|E|)=O(1)+O(|E|)=O(|E|)时间。
第 5-8 行需要 O(|E|α(|V|)) 时间。
第 9 行需要 O(1) 时间。

所以时间复杂度为：

Answer 1

Could you explain me why we deduce that the time to sort the edges in line 4 is O(E*lgE)?

为了对一组 N 项进行排序，我们使用 O(Nlg(N)) 算法，即快速排序、归并排序或堆排序。因此，为了对 E 条边进行排序，我们需要 O(Elg(E)) 时间。然而，在某些情况下这不是必需的，因为我们可以使用更复杂的排序算法（进一步阅读）。

Also how do we get that the total time complexity is O((V+E)α(V))?

我不认为总复杂度是 O((V+E)α(V))。那将是 5-8 循环的复杂性。 O((V+E)α(V))复杂度来自V MAKE-SET操作和E Union操作。要找出为什么我们将其与 α(V) 相乘，您需要阅读一些算法书籍中对不相交集数据结构的深入分析。

How fast can you make Kruskal's algorithm run?

对于第一部分，第 4 行，我们有 O(E*lg(E)) 复杂度，对于第二部分，第 5-8 行，我们有 O((E+V)α(五））复杂性。这两个加起来产生 O(Elg(E)) 复杂度。如果我们使用 O(N*lg(N)) 排序，这将无法改进。

What if the edges weights are integers in the range from 1 to W for some constant W?

如果是这样的话，那么我们可以在第一部分使用计数排序。给出第 4 行复杂度 O(E+W) = O(E)。在那种情况下，算法的总复杂度为 O((E+V)*α(V))。请注意，实际上 O(E + W) 包含一个常数，该常数可能相当大并且对于大 W 可能不切实际。

How does the time complexity depend on the weight of the edges?

如前所述，如果边的权重足够小，我们可以使用计数排序来加速算法。

EDIT:

In addition, suppose that all edge weights in a graph are integers from 1 to |V|. How fast can you make Kruskal's algorithm run? I have thought the following:

In order the Kruskal's algorithm to run faster, we can sort the edges applying Counting Sort.

The line 1 requires O(1) time. The lines 2-3 require O(vα(|V|)) time. The line 4 requires O(|V|+|E|) time. The lines 5-8 require O(|E|α(|V|)) time. The line 9 requires O(1) time.

你的想法是对的，不过你可以把bounds调小一些。

第 2-3 行需要 O(|V|) 而不是 O(|V|α(|V|))。但是我们在之前的计算中将其简化为O(|V|α(|V|))，以便于计算。

有了这个，您将获得以下时间： O(1) + O(|V|) + O(|V| + |E|) + O(|E|α(|V|)) + O(1) = O(|V| + |E| ) + O(|E|α(|V|))

您可以将其简化为 O((|V| + |E|) * α(|V|) 或 O(|V| + |E|*α(|V|)。

所以虽然你是对的，因为 O((|V| + |E|) * α(|V|) < O((|V| + |E|) * lg(|E|)

|W| 的计算是类似的。

运行 Kruskal 算法的时间

Running time of Kruskal's algorithm

performance

time

graph

kruskals-algorithm