algorithm - 仅查找权重为 1 和 2 的生成树的算法

Question

给定一个加权的、连接的、简单的无向图 G，每条边的权重只有 1 和 2，求 G 在 O(V+E) 中的 MST。有任何想法吗？

抱歉问题的措辞，我尽力翻译它。

Answer 1

在Prim 算法中，您需要一种存储活动边的方法，以便您可以访问和删除权重最低的边。

通常，权重范围很广，并且使用某种堆数据结构来存储边。

但是，在这种情况下，权重是 1 或 2，因此您可以简单地将边存储在 2 个单独的列表中，一个用于权重为 1 的边，第二个用于权重为 2 的边。

要找到权重最低的边，只需从第一个列表中取一个，除非它是空的，在这种情况下，您从第二个列表中取一个边。

从列表中访问和删除元素是 O(1)，因此 Prim 的算法将以 O(V+E) 运行。

Answer 2

当边具有任意权重时，Prim 算法计算最小生成树。

Prim 算法的工作原理是进行一种广度优先搜索，从某个任意节点开始，并将边缘保留在优先级队列中。它不断提取权重最低的边，要么在不扩展搜索的情况下丢弃它（如果边指向树中已经存在的节点），要么将其添加到结果中，将其相反节点标记为树中，然后扩展搜索。

以我刚刚解释的幼稚方式完成，Prim 的算法主要由将|E|边缘入列/出列优先级队列的成本支配。每个入队/出队都需要O(log |E|)时间，因此总的渐近成本是O(|E| log |E|)时间，或者更准确地说，是O(|E| log |E| + |V|).

如果我们有办法在恒定时间内完成这些入队和出队，总运行时间将是O(|E| + |V|)......