好奇两种算法的优劣

Louis_lxy @ 2024-05-27 19:51:03

by Louis_lxy @ 2024-05-27 19:53:51

是因为我 prim 用的是链式前向星而 kruskal 用的是 vector 吗

by 半只蒟蒻 @ 2024-05-27 20:07:59

@ldh270657080 因为两种算法的原理不一样，不妨去看看这两种算法的时间复杂度

by 半只蒟蒻 @ 2024-05-27 20:08:32

应该是在稠密图上跑 Prim 会相对较快

by Igallta @ 2024-05-27 20:09:56

@半只蒟蒻

为什么我是 prim 大于 kruskal？

by Igallta @ 2024-05-27 20:10:20

↑

我指的是用时。

by 半只蒟蒻 @ 2024-05-27 20:11:31

@Igallta 我怎么会知道，你实现有问题呗

by Igallta @ 2024-05-27 20:12:22

@半只蒟蒻

我的意思是那这个楼主指的快不快是玄学罢

by 半只蒟蒻 @ 2024-05-27 20:14:14

@Igallta 我怎么会知道啊

by lunjiahao @ 2024-05-27 20:24:03

@ldh270657080

Prim 时间复杂度 O(n \log n)

Kruskal 时间复杂度 O(m \log m)

你猜哪个快？

by lunjiahao @ 2024-05-27 20:25:40

@Igallta

你这 Prim 时间复杂度 O(n^2) 跑的快就怪了，明明还可以用优先队列优化成 O(n \log n)