找最小生成树的算法思路

假设一个图的边的权值都在1到n的整数范围内，如何设计一种O(n(V+E))的算法来找这个图的最小生成树呢？（ps: 之前发的贴题目有误，实在不好意思！！）
感谢！！！

619899442 发表于 2020-2-5 07:13
In Kruskal Algorithm, instead of sorting edges by weight, build a reverse index (weight -> [edges]), ...

我觉得这个跟bucket sort有点像 但是runtime能不能降到n(V+E)?因为感觉union find总有一个log

kruscal: https://www.youtube.com/watch?v=fAuF0EuZVCk
primm: https://www.youtube.com/watch?v=oP2-8ysT3QQ

syia 发表于 2020-2-5 05:51
kruscal: https://www.youtube.com/watch?v=fAuF0EuZVCk
primm: https://www.youtube.com/watch?v=oP2-8ys ...

谢谢啊！但题目要找的是O(n(V+E))的算法，以上这俩个时间复杂度都不符合哈，有没有其它符合O(n(V+E))时间复杂的算法呢

In Kruskal Algorithm, instead of sorting edges by weight, build a reverse index (weight -> [edges]), and iterate each edge in increasing weight order (from 1 to n).

阿钟 发表于 2020-2-5 08:00
我觉得这个跟bucket sort有点像 但是runtime能不能降到n(V+E)?因为感觉union find总有一个log

path compression + ranking 可以给出近似于Constant time：https://en.wikipedia.org/wiki/Di ... ure#Time_complexity

阿钟 发表于 2020-2-5 08:00
我觉得这个跟bucket sort有点像 但是runtime能不能降到n(V+E)?因为感觉union find总有一个log

哦 inverse ackermann永远 <5, good to know...

619899442 发表于 2020-2-5 07:13
In Kruskal Algorithm, instead of sorting edges by weight, build a reverse index (weight -> [edges]), ...

有点没懂"build a reverse index (weight -> [edges])"，可以再稍微解释一下吗，谢谢啦