Question

What is the greedy choice Prim’s algorithm makes and what property is preserved with each greedy choice?

Answer 1

The Prim's Algorithm follows the greedy approach. The Prim's algorithm maintains two sets of vertices. The first set contains all the vertices which are already included in the minimum spanning tree whereas the second set contains the vertices that are yet to be included.

It follows step wise and starts with an empty spanning tree. After this, it takes one vertices which connects both the sets and then chooses the one which has the least weight edge. This carries on untill it connects all the vertices in the spanning tree. The greedy choise here is that it choses at first only the vertices which have the least value attached to it.

The property which is preserved with each greedy choice is minimum spanning tree. So that the vertices which are selected have the least weight first.

If you liked the solution then give a thumbs up ? it will be really appreciated ?