Example of graph with two different MSPs via Prim’s Algorithm

algorithmscomputer sciencegraph theory

I was discussing Prim's algorithm and Kruskal's algorithm for finding minimum spanning trees the other day and we began to wonder about the conditions under which multiple MSPs would be possible.

We quickly came up with and proved the (apparently famous) fact that unique edge labeling leads to a unique MSP.

However, we wondered if it was possible to create a graph in which Prim's algorithm would create at least two different MSPs if it started from different vertices with the added condition that at no point must it be forced to make "a choice", i.e. choose between two edges available to it that have the same weight?

We believed no but could neither prove it nor come up with a counterexample.

Best Answer

No: the only way Prim's algorithm can end up finding multiple minimum spanning trees is if it has to break a tie between two edges with equal weight.

To see this, let $G$ be any (connected) weighted graph. Let $G'$ be a modification of $G$ in which we add a small offset $\epsilon_i$ to the weight of the $i^{\text{th}}$ edge. Each $\epsilon_i$ should be much smaller than the difference between any two distinct edge weights, and the $\epsilon_i$'s should all be different.

With this construction, $G'$ has a unique minimum spanning tree, since all its edge weights are distinct. Therefore Prim's algorithm can only produce one possible output for $G'$.

Now run Prim's algorithm in parallel on $G$ and $G'$, starting from the same vertex. One of two things must happen:

  1. The spanning tree found by Prim's algorithm is the same for both graphs. If this happens starting at every vertex, this means that Prim's algorithm always finds the same spanning tree for $G$ - since it certainly always finds the same spanning tree for $G'$.

  2. Starting at some vertex, the spanning tree found for $G$ is different from the spanning tree found for $G'$. For this to happen, there must be a step where the $\epsilon_i$ adjustments in $G'$ made a difference. Since the adjustments are much smaller than the difference between distinct edge weights, they can only make a difference when, in $G$, we choose between two edges of equal weight.

To put it differently: if you're consistent about how you break ties between edges (which is what the $\epsilon_i$'s accomplish) then you get the same spanning tree no matter where you start.

Related Question