Prim's MST: Does the start node matter?

Question

I intuitively feel that if one is using Prim's algorithm to find a graph's minimum spanning tree, it doesn't matter which root node is picked - the resultant MST will have the same weight regardless. Is this correct?

Delacourt

Another way to think about why this works is: We need to select all vertices for spanning tree anyway. So even if you start with vertex which has an edge with huge weight, it doesnt matter because that vertex had to be selected either way. As long as you follow greedy approach, the min weight will be honored, however the shape(aka edges selected) might change as others mentioned. – Reposeful

Answer 1

That is correct. Choosing a different starting node could give you a different spanning tree, but it will always have the same weight: the minimal possible.

Braca

Answer 2

This is because of uniqueness of minima.

Proof:

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.

Eon

Answer 3

The weight / cost of the Tree will be the same regardless of starting node/vertex; however, the shape of the tree may differ. When two edges up for candidacy have the same weight that ends up being the current minimum, the choice depends on the implementation. Unless there's a true tie-breaking step (which is unlikely; in graphs with many equal-weight edges this could take up to O(n), for no real gain), it is most likely "first found". This means the order in which nodes/verteces are added and visited matters for the tie-breaking and thus the starting node/vertex can affect the shape.

Secondly, it could affect performance, but this is hard to control. As heap operations become more expensive with their size, you'd want to add as few edge as possible, especially early on. One could use this as a rationale to give priority to low-degree verteces. However, this is unlikely to matter much beyond the first node/vertex.

TL;DR: For the total Cost/Weight: No. For the shape: Yes, if there are multiple MSTs.

Lacuna