Wikia

Math Wiki

Proof of Prim's algorithm

Talk0
876pages on
this wiki

Prim's algorithm yields a minimal spanning tree.

ProofEdit

Let T be the spanning tree on G generated by Prim's algorithm, which must be proved to be minimal, and let T' be spanning tree on G, which is known to be minimal.

If T = T', then T is minimal.

If T \ne T', let e_k = (u,v) be the first edge chosen by Prim's algorithm which is not in T', chosen on the k'th iteration of Prim's algorithm. Let P be the path from u to v in T', and let e* be an edge in P such that one endpoint is in the tree generated at the k-1'th iteration of Prim's algorithm and the other is not, i.e., one endpoint of e* is u or one endpoint is v, but the endpoints are not u and v.

If the weight of e* is less than the weight of e_k, then Prim's algorithm would have chosen it on its kth iteration, so it is certain that w(e*) \ge w(e_k). In particular, when e* has weight equal to that of e_k, the choice between the two is arbitrary. Whether the weight of e* is greater than or equal to e_k, e* can be substituted with e_k while preserving minimal total weight of T'. This process can be repeated indefinitely, until T' is equal to T, and it is shown that the tree generated by any instance of Prim's algorithm is a minimal spanning tree.

QED

Around Wikia's network

Random Wiki