graph - プリムのMST：開始ノードは重要ですか？

Question

プリムのアルゴリズムを使用してグラフの最小スパニングツリーを見つける場合、どのルートノードを選択するかは問題ではなく、結果の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

ツリーの重み/コストは、開始ノード/頂点に関係なく同じになります。ただし、木の形は異なる場合があります。候補の2つのエッジが同じ重みを持ち、最終的に現在の最小値になる場合、選択は実装によって異なります。真のタイブレークステップがない限り（これはありそうにありません。同じ重みのエッジが多数あるグラフでは、実際のゲインがない場合、これはO（n）までかかる可能性があります）、「最初に見つかった」可能性があります。これは、ノード/頂点が追加されて訪問される順序がタイブレークの問題であり、したがって開始ノード/頂点が形状に影響を与える可能性があることを意味します。

第二に、パフォーマンスに影響を与える可能性がありますが、これを制御するのは困難です。ヒープ操作はサイズが大きくなるにつれてコストが高くなるため、特に早い段階で、エッジをできるだけ少なくする必要があります。これを理論的根拠として使用して、低度の頂点を優先することができます。ただし、これが最初のノード/頂点を超えて問題になる可能性はほとんどありません。

TL; DR：総コスト/重量の場合：いいえ。形状の場合：はい、複数のMSTがある場合。