是因为我 prim 用的是链式前向星而 kruskal 用的是 vector 吗
by Louis_lxy @ 2024-05-27 19:53:51
@[ldh270657080](/user/1203411) 因为两种算法的原理不一样，不妨去看看这两种算法的时间复杂度
by 半只蒟蒻 @ 2024-05-27 20:07:59
应该是在稠密图上跑 Prim 会相对较快
by 半只蒟蒻 @ 2024-05-27 20:08:32
@[半只蒟蒻](/user/112049)
为什么我是
[prim](https://www.luogu.com.cn/record/101304189)
大于
[kruskal](https://www.luogu.com.cn/record/127290950)？
by Igallta @ 2024-05-27 20:09:56
↑
我指的是用时。
by Igallta @ 2024-05-27 20:10:20
@[Igallta](/user/813622) 我怎么会知道，你实现有问题呗
by 半只蒟蒻 @ 2024-05-27 20:11:31
@[半只蒟蒻](/user/112049)
我的意思是那这个楼主指的快不快是玄学罢
by Igallta @ 2024-05-27 20:12:22
@[Igallta](/user/813622) 我怎么会知道啊
by 半只蒟蒻 @ 2024-05-27 20:14:14
@[ldh270657080](/user/1203411)
Prim 时间复杂度 $O(n \log n)$
Kruskal 时间复杂度 $O(m \log m)$
你猜哪个快？
by lunjiahao @ 2024-05-27 20:24:03
@[Igallta](/user/813622)
你这 Prim 时间复杂度 $O(n^2)$ 跑的快就怪了，明明还可以用优先队列优化成 $O(n \log n)$
by lunjiahao @ 2024-05-27 20:25:40