我想知道是否可以通过在该图上执行 Prim 算法来提供图 G 的任何最小生成树？
Prim 算法是否为我们提供了所有可能的 MST？
问问题
528 次
3 回答
0
于 2012-08-27T12:27:34.757 回答
0
由于Prim 的算法从加权、连接、无向图构造 MST，是的，您可以使用它从这样的图中获得最小生成树。如果您的图表未连接，它将无法工作（但任何其他算法也不会，因为没有生成树，那么）。如果您的图表没有加权，它只会创建一个生成树。
于 2012-08-27T12:28:11.670 回答
0
如果您使用 Prim 的一次来获得 MST，则删除一条边。然后再次使用 prim 来查看是否仍然可以获得相同长度的 MST。如果这样做，请重复，否则将边缘放回并移除另一条边缘。它会很慢......也许只去除沉重的边缘？
于 2012-08-27T12:40:22.340 回答