algorithm - 图算法：Prim

Question

我想知道是否可以通过在该图上执行 Prim 算法来提供图 G 的任何最小生成树？

Prim 算法是否为我们提供了所有可能的 MST？

Answer 1

我想知道是否可以通过在该图上执行 Prim 算法来提供图 G 的任何最小生成树？

是的。

众所周知，Prim 算法是找到最小生成树的好算法。

Answer 2

由于Prim 的算法从加权、连接、无向图构造 MST，是的，您可以使用它从这样的图中获得最小生成树。如果您的图表未连接，它将无法工作（但任何其他算法也不会，因为没有生成树，那么）。如果您的图表没有加权，它只会创建一个生成树。

Answer 3

如果您使用 Prim 的一次来获得 MST，则删除一条边。然后再次使用 prim 来查看是否仍然可以获得相同长度的 MST。如果这样做，请重复，否则将边缘放回并移除另一条边缘。它会很慢......也许只去除沉重的边缘？