图算法：Prim

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

Prim算法给我们提供了所有可能的MST吗？

我不明白。你问“如果有多于一个MST，是从'random'选择的prim生成的MST吗？”？ – amit

不，我知道我们可以有多个MST，但是Prim算法能否给我们提供所有可能的MST？ – streaming116

可能存在指数级的MST。想想所有权重= 1的集团。 Prim是多项式，所以答案是否定的 - 它不会给你*全部* MSTs – amit

我在想图G中的任何最小生成树是否可以是由在此图上执行算法Prim提供？

Prim算法被称为是一个很好的算法来寻找最低生成树。

2012-08-27 12:27:34 nurettin

你能证明它吗？ – streaming116

我真的不认为这是OP之后的事情。 – amit

对我来说很明显，一个迭代地去除边缘同时保持距离（或权重）不变的算法最终会给MST。 – nurettin

由于Prim's algorithm从一个加权的，连通的无向图构建了一个MST，可以，您可以使用它从这样的图中获取最小生成树。如果图形没有连接，它将不起作用（但是因为没有生成树，所以也不会有任何其他算法）。如果你的图不是加权的，它只会创建一个生成树a。

2012-08-27 12:28:11 Joey

我想用它来拥有所有的MST ...... – streaming116

如果您使用Prim的一次获取MST，然后删除边缘。然后再次使用prim来查看是否仍然可以获得相同长度的MST。如果你这样做，重复，否则把边缘放回去除另一个边缘。它会变慢...也许只能消除重的边缘？

2012-08-27 12:40:22

回答