leetcode 1584号问题
来源：11-11 本章小结和更多关于最小生成树问题的讨论
慕运维9331189
2020-11-02
bobo老师，这道题我开始是用kruskal算法写的，复杂度ElogE，然后超时了。
我在看了题解之后，学会了prim算法还有一种实现方式，复杂度是V²级别的。
我想问一下bobo老师，这个写法一般只适用于稠密图吗？
个人理解：
通常情况下我们处理的图都是稀疏图，也就是边的个数和点的个数差不多，不会有数量级的差距（大致理解为V≈E）。所以这时ElogE的复杂度是要比V²好的。
而当图非常稠密时，有E=V²，这时ElogE的复杂度反而不如V²了。
写回答
1回答
-
1
是的，只适用于稠密图；
2
你的理解非常正确。
但是，这个问题用 kruskal 也能通过，我的参考代码（C++）：https://github.com/liuyubobobo/Play-Leetcode/blob/master/1584-Min-Cost-to-Connect-All-Points/cpp-1584/main.cpp
（Leetcode C++ 速度比 Java 慢，同样的算法，用 C++ 能通过，用 Java 近乎一定能通过。）
继续加油！：）
00
相似问题
leetcode 127号问题
回答 1
用C语言实现leetcode785号问题
回答 1
leetcode问题
回答 1
关于一题leetcode问题
回答 1
leetcode 1263问题
回答 1