algorithm - 何时使用 Kruskal 算法与 Prim 算法

Question

可能的重复：
Kruskal vs Prim

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

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

Answer 1

一个重要的区别：如果您的图表断开连接，Prim 对您没有好处（需要连接图表）。另一方面，Kruskal 将适用于连通图或不连通图。在后一种情况下，它会找到最小生成森林，即每个连接组件的 MST。