Prim's MST: Does the start node matter?

graph minimum-spanning-tree prims-algorithm
Nick Heiner picture Nick Heiner · Nov 24, 2009 · Viewed 7k times · Source

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?

Answer

Mark Byers picture Mark Byers · Nov 24, 2009

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.

Related questions

Difference between Prim's and Dijkstra's algorithms?

What is the exact difference between Dijkstra's and Prim's algorithms? I know Prim's will give a MST but the tree generated by Dijkstra will also be a MST. Then what is the exact difference?

Read More
Time complexity of Prim's MST Algorithm

Can someone explain to me why is Prim's Algorithm using adjacent matrix result in a time complexity of O(V2)?

Read More
Is Minimum Spanning Tree afraid of negative weights?

This is a follow-up question of Why most graph algorithms do not adapt so easily to negative numbers?. I think Shortest Path (SP) has problem with negative weights, because it adds up all weights along the paths and tries to …

Read More