leetcode 1584号问题

Question

bobo老师，这道题我开始是用kruskal算法写的，复杂度ElogE，然后超时了。
我在看了题解之后，学会了prim算法还有一种实现方式，复杂度是V²级别的。

我想问一下bobo老师，这个写法一般只适用于稠密图吗？

个人理解：
通常情况下我们处理的图都是稀疏图，也就是边的个数和点的个数差不多，不会有数量级的差距（大致理解为V≈E）。所以这时ElogE的复杂度是要比V²好的。
而当图非常稠密时，有E=V²，这时ElogE的复杂度反而不如V²了。

Answer 1

liuyubobobo 2020-11-03 13:21:15

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 近乎一定能通过。）

继续加油！：）