Prime算法和Kruscal算法的区别如下:
Prime算法在稠密图中比Kruskal算法好,在稀疏图中Prime算法比Kruskal算法差。
Prime算法+Heap算法在任何时候都有令人满意的的时间复杂度,但是代价是空间消耗极大。
时间复杂度并不能反映出一个算法的实际优劣。
如图所示:
总结:若是所给的题大多数是稀疏图,所以尽可能地使用Prime算法+Heap算法吧,在稀疏图中这是无敌的。如果一定要在朴素Prim和Kruskal里选一个的话那就用Kruskal吧。当然Prime的代码比较简单,比较简单的题用Prim也无所谓,只要不是极稀疏图的题两者相差都不大。