关于一种最小生成树的新算法
  • 板块学术版
  • 楼主pour_demain
  • 当前回复28
  • 已保存回复30
  • 发布时间2025/6/19 18:04
  • 上次更新2025/6/20 18:05:07
查看原帖
关于一种最小生成树的新算法
857298
pour_demain楼主2025/6/19 18:04

闲着没事的时候想的,不确定是否正确哈

我们输入的时候统计每个节点的度,每次操作先找到度为 11 的节点,将它与和它直连的边从原图中删除,加入到最小生成树中,然后再去找现在最短的边,把这条边删除并加入到最小生成树中。

如果可以在 O(1)O(1) 的时间内找到度为 11 的节点和最短的边,那么整个复杂度应该是 O(n)O(n) ,因为很明显的是每次至少加入一条边。

现在的问题就是怎样在 O(1)O(1) 的时间内找到度为 11 的节点和最短的边,但就算是 O(logn)O(\log{n}) 的时间,总时间为 O(nlogn)O(n\log{n}) 也应该比prim算法的 O(E+VlgV)O(E+V\lg{V}) 快吧。

2025/6/19 18:04
加载中...