添加新节点后如何查找MST？

| 添加新节点或更改路径距离后如何找到“ 0”？ 我需要帮助解决此问题。有谁能够帮助我？ 谢谢。     
2020-01-16 2 条评论
分享

没有找到相关结果

    已邀请:

    稀瓣囊

    添加新边缘时： 您将需要执行图形遍历，最简单的方法是从已修改/新边的一侧进行DFS遍历。如果可以返回到以前的节点，那么您将有一个循环。 在该循环中，您将需要移除最大的边缘。您将再次得到一棵树，它是最小的跨树。 如果要更改边缘权重，则需要： 通过临时移除新边，将图形分为两个部分，A和B。 如果新边缘的权重比以前小，则可以放回原处。否则： 遍历之前处理过的边，并检查它们是否将A结合到B。 从那些边缘中选择最小的边缘，然后使用该边缘连接组件。 同样，您将获得一个新的最小生成树。 总体而言，这是
    O(V+E)
    ，乘以逆阿克曼反演的小倍。     
    2020-01-16 0 0
    分享
    为什么被折叠? 0 个回复被折叠

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

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