Member Avatar for drichird

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:

1. Assume a growing, subset tree that both Kruskal and MST have in common.
2. 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).
3. The MST must eventually reach y using an edge "f" not in Kruskal (MST + e form a cycle with edge f in MST).
4. Since f came after e, it must be that cost f >= cost e.
5. Since MST + e froms a cycle through y, replace f with e in the MST and you still have an MST
6. 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 a simpler proof for Prim?

  • 2 Contributors
  • 1 Reply
  • 455 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by sarehu
sarehu commented: An interesting question! +1
Member Avatar for sarehu

1. Assume a growing, subset tree that both Kruskal and MST have in common.
2. 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).

What do you mean by "the first edge added by Kruskal that does not yield an MST?" Every edge added by Kruskal's algorithm does not yield a minimum spanning tree, _except_ for the last edge added. What do you mean by "first"?

Also, in step one, you refer to a subset tree that both "Kruskal and MST have in common." What does 'Kruskal' mean in this sentence? Kruskal is the name of a person or the name of an algorithm. You're referring to a subset tree that Kruskal's algorithm is in the process of building?

I am being pedantic, but your wording must be precise if you are to convince yourself that you're thinking clearly. And you should always be critical of your wording.

3. The MST must eventually reach y using an edge "f" not in Kruskal (MST + e form a cycle with edge f in MST).
4. Since f came after e, it must be that cost f >= cost e.
5. Since MST + e froms a cycle through y, replace f with e in the MST and you still have an MST
6. Repeat process and eventually the MST morphs into Kruskal

You're using the word "MST," which I take it means "minimum spanning tree." You mean to refer to simply a "spanning tree," not a "minimal spanning tree," right? Because if it's not minimal, it's not an MST.

Is the proof for Prim identical? Since the Prim algorithm is more constrained, it seems to me there should be a simpler proof for Prim?

It's pretty much the same kind of idea, so it takes the same length. (And the proof in both cases is short anyway.) For Prim's algorithm, let S be the set of nodes in the subtree you're building, S' be the rest of the nodes. Let F be the set of edges with one node in S and one node in S'. You can show that if you didn't pick the smallest edge in F, then you could add it later and remove one of the edges in F.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.