克鲁斯卡尔算法如下：
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
根据我的教科书：
在第 1 行初始化集合 A 需要 O(1) 时间，在第 4 行对边进行排序的时间是 O(E lgE)。第 5-8 行的 for 循环对不相交集森林执行 O(E) FIND-SET 和 UNION 操作。随着 |V| MAKE-SET 操作，这些操作总共需要 O((V+E)α(V)) 时间，其中 α 是一个增长非常缓慢的函数。因为我们假设 G 是连通的，所以我们有 |E| <= |V|-1，因此不相交集操作需要 O(E α(V)) 时间。此外，由于α(V)=O(lgV)=O(lgE)，Kruskal算法的总运行时间为O(E lgE)。观察到 |E|<|V|^2，我们有 lg |E|=O(lgV)，因此我们可以将 Kruskal 算法的运行时间重述为 O(E lgV)。
你能解释一下为什么我们推断在第 4 行中对边缘进行排序的时间是 O(E lgE) 吗？另外，我们如何得到总时间复杂度为 O((V+E)α(V)) ？
此外，假设图中的所有边权重都是从 1 到 |V| 的整数。你能让 Kruskal 的算法运行多快？如果对于某个常数 W，边权重是从 1 到 W 范围内的整数怎么办？
时间复杂度如何取决于边的权重？
编辑：
此外，假设图中的所有边权重都是从 1 到 |V| 的整数。你能让 Kruskal 的算法运行多快？
我想到了以下几点：
为了使 Kruskal 算法运行得更快，我们可以应用计数排序对边进行排序。
- 第 1 行需要 O(1) 时间。
- 第 2-3 行需要 O(v) 时间。
- 第 4 行需要 O(|V|+|E|) 时间。
- 第 5-8 行需要 O(|E|α(|V|)) 时间。
- 第 9 行需要 O(1) 时间。
因此，如果我们使用计数排序来解决边缘，Kruskal 的时间复杂度将是
你能告诉我我的想法是否正确吗？
还：
如果对于某个常数 W，边权重是从 1 到 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) 时间。
所以时间复杂度为：
