设计一种算法，在线性时间内找到该图的最小生成树

Question

我正在研究一个问题，在这个问题中，我得到了一个有 n 个顶点和 m 条边的无向图 G，这样每条边 e 的权重 w(e) ∈ {1, 2, 3}。任务是设计一种算法，在线性时间 (O(n + m)) 内找到 G 的最小生成树。

到目前为止，这些是我的想法：

在我目前正在学习的算法图论课程中，我们已经涵盖了 Kruskal 和 Prim 的 MST 算法。也许我可以以某种方式修改这些，以获得线性时间。
边缘的排序通常需要对数线性（O（mlog（m）））时间；然而，由于所有边的权重都是 1、2 或 3，因此桶排序可用于按边数 (O(m)) 对边进行时间线性排序。

我正在使用以下版本的 Kruskal 算法：

Kruskal(G)
  for each vertex  ∈  do MAKE−SET()
  sort all edges in non-decreasing order
  for edge ,  ∈  (in the non-decreasing order) do
    if FIND  ≠ FIND() then 
      colour (, ) blue
      UNION(, )
  od
  return the tree formed by blue edges

此外，MAKE-SET(x)、UNION(x, y) 和 FIND(x) 定义如下：

MAKE-SET()
  Create a new tree rooted at 
  PARENT()=x

UNION(, )
  PARENT FIND() ≔ ()

FIND()
   ≔ 
  while  ≠ PARENT() do
     ≔ PARENT()
  return y

我目前遇到的问题是，虽然我可以在线性时间内实现 Kruskal 的前两行，但我还没有设法为算法的后四行做同样的事情（来自 'for edge u, ...' 直到 'UNION (u, v)').

对于如何在线性时间内实现算法的其余部分，或者如何在线性时间内找到 Kruskal 算法（或其他一些最小生成树算法）的修改，我将不胜感激。

谢谢。

Answer 1

如果你使用Disjoint Sets data structure with both path compression and union by rank, you get a data structure whose each operation's complexity grows extremely slowly - it is something like the inverse of the Ackermann function，并且对于宇宙中原子的估计数量等尺寸来说并不是那么大。实际上，每个操作都被认为是常数时间，因此算法的其余部分也被认为是线性时间。

来自同一篇维基百科文章

Since α(n) is the inverse of this function, α(n) is less than 5 for all remotely practical values of n. Thus, the amortized running time per operation is effectively a small constant.

设计一种算法，在线性时间内找到该图的最小生成树

Design an algorithm which finds a minimum spanning tree of this graph in linear time

sorting

algorithm

graph

time-complexity

minimum-spanning-tree