何时使用 Kruskal 算法与 Prim 算法

Question

可能的重复：
克鲁斯卡尔 vs 普里姆

你什么时候会使用 Kruskal 算法而不是 Prim 算法来找到最小生成树？哪种输入图和节点更适合每种类型？在什么情况下，在空间和时间方面使用其中之一更有效？

他们的特定输入是否使一个比另一个好得多？

Answer 1

一个重要的区别：如果您的图形断开连接，则 Prim 对您没有任何好处（需要连接图形）。另一方面，Kruskal 将在连通图或断开图上工作；在后一种情况下，它找到最小生成森林，每个连接组件的 MST。