MST的线性时间算法

Question

我想知道是否有人可以指向线性时间算法,以便在存在少量权重时找到图形的MST(即边缘只能有2个不同的权重).

除了Prim's,Kruskal's,Boruvka之外,我在google上找不到任何东西,其中似乎没有任何属性会减少这种特殊情况下的运行时间.我猜它是线性时间,它必须是对BFS的某种修改(当权重均匀时找到MST).

Answer 1

lg VPrim 运行时的影响因素O(V lg V)是用于查找下一个候选边的堆。我非常确定，可以设计一个优先级队列，当可能的权重数量有限时，它可以在恒定时间内执行插入和删除操作，这会将 Prim 减少到O(V)。

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