这个问题在这里已有答案：
我最近一直在研究Prims / Kruskals算法，以便在图中找到最小生成树，我对以下问题感兴趣：
Let G be an undirected graph on n vertices with m edges, such that each edge has a weight w(e) ∈ {1, 2, 3}. Is there an algorithm which finds a minimum spanning tree of G in time O(n+m)?
显然，您可以在图表上运行Prims，并且您将得到最小生成树，但不是在所需的时间内 .
我认为我们可以首先将每个重量为1的边添加到树上，只要它没有产生循环，好像有一个重量1的边没有产生循环，那么它最好是重量2的边说，并按递增顺序执行此操作 .
任何有关设计算法的可能方法的帮助都将受到赞赏，任何实现（java更可取但欢迎任何语言）都会非常有用 .
1 回答
您正在描述Kruskal算法的一个微小变化，它使得m边缘的重量O（m）排序成本，因为您只需要将边缘放在3个桶中 .
由于disjoint set data structure具有惊人的特性，因此Kruskal的其余部分几乎都是O（m），所以你应该保持良好状态 .
构建树本身应该是O（m）而不是O（n m），因为没有必要处理顶点 . 例如 . 如果你在一个巨大的顶点上有一些边缘，大多数没有连接，如果你对数据结构设计很小心，后者不需要增加算法成本 .