I teach a course in Discrete Mathematics, and part of the subject matter is a coverage of Prim's algorithm and Kruskal's algorithm for constructing a minimum spanning tree on a weighted graph. Students do not actually implement the algorithms in code; only pseudocode is given; students are asked to hand-trace the algorithm behaviors on a number of exercise and assessments.
In order to make the algorithms deterministic (and so exercises each have a unique solution), the textbooks I've seen generally give a further direction of, "assume that the vertices are ordered alphabetically" (e.g., Rosen Sec. 11.4 exercises 13-15). That is, this presents a deterministic tiebreak criterion, assuming edges are identified with letters themselves in alphabetical order. E.g.: if at some step of either algorithm, $\{a, d\}$ and $\{b, c\}$ are both eligible edges to be added with minimum weight, then the $\{a, d\}$ edge will be chosen. (Here's an example student question arising from this direction.)
I've personally implemented both algorithms in C++ following this criterion, using an adjacency matrix for the underlying edge data. I've found that the exercise direction is clarified for students when we step through a minimal-search loop at least once, with the vertices stored in alphabetical order, and find that the selected edge is the first one found with minimal value.
So my question is: Do the algorithms of Prim and Kruskal always produce the same minimum spanning tree, given the tiebreak-by-alphabetical order criterion? (And ignoring any other possible implementation details.)
My first intuition was that I could sketch an example where the two algorithms produce different trees, but after several attempts I've failed to do so. I also wrote a Monte Carlo program to randomly create a few hundred thousand random weighted graphs, of various vertex, edge, and weight numbers, and send them through my implementation of both Prim's and Kuskal's algorithm; in all of my experimentation, they've produced identical minimum spanning trees.
Some things that are obviously known and not part of this question:
- Prim and Kruskal will of course produce trees of the same total weight. This question is about whether the trees themselves are identical, using all the same edges.
- Prim and Kruskal will of course produce identical trees if the edge weights are all unique. Clearly any counterexample graph requires at least some edges with equal weight.
- Prim and Kruskal may add edges in a different order; it's easy to produce examples of that. This question is whether the final resulting spanning tree is always the same.
Here are some related questions, answers, and comments which do not resolve this question. None of these answers assume the deterministic ordering (alphabetic) criterion here, and therefore conclude that the ordering is ambiguous due to different possible underlying implementations:
Best Answer
Yes, because a tiebreaker can be modeled as changing the edge weights very slightly to make all edge weights unique.
Suppose that edges $e_1, e_2, \dots, e_m$ have weights $w_1, w_2, \dots, w_m \in \mathbb R$. Let $\epsilon$ be the smallest difference between two distinct edge weights. Suppose also that we've written edges $e_1, e_2, \dots, e_m$ in the tiebreaking order: whenever we are choosing between edges $e_i$ and $e_j$ with the same weight, we pick $e_i$ if $i<j$ and $e_j$ otherwise.
This decision process is equivalent to the decision process where edge $e_i$ has weight $w'_i = w_i + \frac{i}{2m} \cdot \epsilon$. The weights $w_1', w_2', \dots, w_m'$ are all unique, but comparing $w_i'$ and $w_j'$ is equivalent to comparing $w_i$ and $w_j$ when $w_i \ne w_j$. Only when $w_i = w_j$ does the extra term $\frac{i}{2m} \cdot \epsilon$ come into effect, and using it to compare is equivalent to using the tiebreaker.
So Kruskal with tiebreaks is equivalent to Kruskal with weights $w_1', \dots, w_m'$. This is equivalent to Prim with weights $w_1', \dots, w_m'$, because there is only one MST when weights are unique. That, in turn, is equivalent to Prim with the same tiebreaks.