algorithm - MST 的线性时间算法

Question

我想知道是否有人可以指出线性时间算法来在权重数量较少时找到图的 MST(即边只能有 2 个不同的权重)。

除了 Prim 的、Kruskal 的和 Boruvka 的，我在谷歌上找不到任何东西，在这种特殊情况下，它们似乎都没有任何可以减少运行时间的属性。我猜想让它成为线性时间，它必须对 BFS 进行某种修改(当权重均匀时找到 MST)。

Answer 1

lg V 的原因Prim 的因素 O(V lg V) runtime 是用于查找下一个候选边的堆。我很确定可以设计一个优先级队列，当可能的权重数量有限时，它可以在固定时间内插入和删除，这会将 Prim 减少到 O(V) .

对于优先级队列，我相信一个数组就足够了，该数组的索引涵盖所有可能的权重，其中每个元素指向一个链表，该链表包含具有该权重的元素。你仍然有一个因子 d (不同权重的数量)用于确定从哪个列表中获取下一个元素(“最低”非空元素)，但如果 d是一个常数，那么你会没事的。