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

Question

我直观地觉得，如果使用 Prim 的算法来查找图的最小生成树，那么选择哪个根节点都没有关系 - 生成的 MST 无论如何都会具有相同的权重。这个对吗？

Answer 1

那是对的。选择不同的起始节点可能会给你一个不同的生成树，但它总是具有相同的权重：最小的可能。

Answer 2

这是因为minima 的唯一性。

证明：

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。