普里姆最小生成树算法：起始节点是否重要？

Question

我直觉地感觉，如果使用Prim算法来找到一个图的最小生成树，那么选择哪个根节点并不重要——结果生成的最小生成树的权重是相同的。这个理解对吗？

- Nick Heiner

---

另一种思考这个问题的方式是：我们需要选择所有顶点来构建生成树。因此，即使您从一条权重非常大的边开始，也无所谓，因为该顶点必须被选择。只要您遵循贪心法则，最小权重就会得到尊重，但形状（也就是所选的边）可能会发生变化，正如其他人所提到的那样。 - theprogrammer

Answer 1

没错。选择不同的起始节点可能会给你不同的生成树，但它们的权重始终相同：最小可能值。

- Mark Byers

Answer 2

这是因为最小值的独特性。

证明：

Suppose there are 2 "different" minimum weights W1 and W2

W1 is minimum 
W2 is minimum
W1 != W2

This leads to contradiction because 
if W1 != W2 then 
   W1 < W2  -> W1 is minima
   or 
   W1 > W2  -> W2 is minima
Hence if W1 must equal W2.

- Pratik Deoghare

Answer 3

树的权重/成本不受起始节点/顶点的影响，但是树的形状可能会有所不同。当两条候选边具有相同的权重且成为当前最小值时，选择取决于实现方式。除非存在真正的打破平局的步骤（这不太可能；在具有许多等权重边的图中，这可能需要O(n)时间，却没有真正的收益），否则最可能是“先找到的”。这意味着添加和访问节点/顶点的顺序对于打破平局、进而影响起始节点/顶点和形状很重要。

其次，它可能会影响性能，但这很难控制。随着堆操作的大小变得更加昂贵，您希望尽可能少地添加边缘，特别是早期。一个理由是优先处理低度数的顶点。然而，除第一个节点/顶点外，这很可能不重要。

总之：对于总成本/权重: 否。对于形状: 是，如果有多个最小生成树。

- Gaminic