It's tough being 50 and back in college! If anyone has recently taken an Algorithm class, my question is this: Is the proof for Prim's algorithm any different than for Kruskal? I understand both algorithms are greedy in the sense of picking the least weight edge each itiration. Prims only adds the next least expensive edge that can connect to the existing, growing subtree, whereas Kruskal just picks the next least cost edge period, as long as it creates no cycles, so that eventually all subtrees connect.
I am finding many proofs for Kruskal (e.g. Wikipedia), but trouble finding proofs for Prim. The Kruskal proof is as far as I can see, in plain English:
- Assume a growing, subset tree that both Kruskal and MST have in common.
- Look at the first edge "e" = (x,y) added by Kruskal that does not yield an MST (vertex x is in common subset, vertex y is not).
- The MST must eventually reach y using an edge "f" not in Kruskal (MST + e form a cycle with edge f in MST).
- Since f came after e, it must be that cost f >= cost e.
- Since MST + e froms a cycle through y, replace f with e in the MST and you still have an MST
- Repeat process and eventually the MST morphs into Kruskal
Is the proof for Prim identical? Since the Prim algorithm is more constrained, it seems to me there should be ...