Prim 的 MST：起始节点重要吗？

Question

我直观地感觉到，如果使用 Prim 算法来查找图的最小生成树，那么选择哪个根节点并不重要 - 无论如何，生成的 MST 将具有相同的权重。这是正确的吗？

Answer 1

这是正确的。选择不同的起始节点可能会产生不同的生成树，但它始终具有相同的权重：尽可能小的权重。

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.

Answer 3

无论起始节点/顶点如何，树的权重/成本都将相同；然而，树的形状可能不同。当候选资格的两条边具有相同的权重且最终成为当前最小值时，选择取决于实现。除非存在真正的打破平局的步骤（这不太可能；在具有许多等权边的图中，这可能需要 O(n)，没有真正的增益），否则它很可能是“首先找到”。这意味着添加和访问节点/顶点的顺序对于打破平局很重要，因此起始节点/顶点可以影响形状。

其次，它可能会影响性能，但这很难控制。随着堆操作随着其大小而变得更加昂贵，您需要添加尽可能少的边缘，尤其是在早期。人们可以以此作为优先考虑低度顶点的基本原理。然而，除了第一个节点/顶点之外，这不太重要。

TL;DR：对于总成本/重量：否。对于形状：是，如果有多个 MST。