FANDOM


Prim's algorithm yields a minimal spanning tree.

Proof

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 $ k $th 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

Community content is available under CC-BY-SA unless otherwise noted.