Search code examples
graphminimum-spanning-treeprims-algorithm

Prim's MST: Does the start node matter?


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?


Solution

  • 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.