具有O(kn + m)时间复杂度的Prim算法的修改版本

Question

你能帮我解决这个问题吗?

给定一个无向图G，连通，有加权边，使得权值在[1,k]内为整数。编写Prim算法的修改版本，在O(kn+m)时间内返回最小生成树。

注意:

• n表示顶点数
• m表示边数

Answer 1

你应该使用边缘长度的有限范围。这将帮助您更有效地保持边的优先队列。记住，算法中最重要的一步是找到最小权值的边，这条边连接到目前为止构建的树中尚未添加到树中的节点。尝试使用计数排序作为灵感。