闲着没事的时候想的,不确定是否正确哈
我们输入的时候统计每个节点的度,每次操作先找到度为 1 的节点,将它与和它直连的边从原图中删除,加入到最小生成树中,然后再去找现在最短的边,把这条边删除并加入到最小生成树中。
如果可以在 O(1) 的时间内找到度为 1 的节点和最短的边,那么整个复杂度应该是 O(n) ,因为很明显的是每次至少加入一条边。
现在的问题就是怎样在 O(1) 的时间内找到度为 1 的节点和最短的边,但就算是 O(logn) 的时间,总时间为 O(nlogn) 也应该比prim算法的 O(E+VlgV) 快吧。