Prim的算法和MST

如何描述具有V顶点和E边缘的图形族，其中确认了Prim算法的优先级队列实现的最坏情况运行？     
2019-11-04 2 条评论
分享

没有找到相关结果

    已邀请:

    惭法搽

    好吧，如果不确切知道特定的实现是什么样的，很难说，但如果我没记错Prim的话，你总是需要在确定MST时检查Θ（E）边缘。如果优先级队列实现为二进制堆（这是标准方式），那么每个“检查”都是O（log V），因此总是发生O（E * log V）的最坏情况运行时间。     
    2019-11-04 0 0
    分享
    为什么被折叠? 0 个回复被折叠

    要回复问题请先登录或注册

    或代码 OrCode.com 备案号：粤ICP备15020848号-1
    Escape time: 0.037210941314697