你能帮帮我解决这个问题吗?
给定无向图G,用加权边连接,使得权重在[1,k]中是整数 . 编写Prim算法的修改版本,以O(kn m)时间返回最小生成树 .
注意:
n表示顶点数
m表示边数
您应该使用有限的边长范围 . 这将有助于您更有效地保留边缘的优先级队列 . 请记住,算法中最重要的一步是找到连接到目前为止构建的树的最小权重边缘与尚未添加到树中的节点 . 尝试使用counting sort作为灵感 .
1 回答
您应该使用有限的边长范围 . 这将有助于您更有效地保留边缘的优先级队列 . 请记住,算法中最重要的一步是找到连接到目前为止构建的树的最小权重边缘与尚未添加到树中的节点 . 尝试使用counting sort作为灵感 .