I am studying about MST algorithms. I am curious to find the key differences between prims and boruvka's algorithm but the resources online don't have much to say about them other than their implementation and algorithm. If someone can explain, it would be great help. Thanks!
1 Answers
Both algorithms use the facts that
For every vertex v, there exists a minimum spanning tree T such that the cheapest edge incident to v belongs to T.
For every edge e, the (minimum) spanning trees that contain e are in natural one-to-one correspondence with the (minimum) spanning trees of the graph where e is contracted.
Prim and Borůvka exploit these facts in different ways. Prim chooses a root vertex r and repeatedly contracts the cheapest edge incident to r (the usual description avoids graph contraction but is equivalent to this) until only r remains. Borůvka repeatedly contracts all of the cheapest incident edges "in parallel" until there is exactly one vertex remaining.
You can create a variety of minimum spanning tree algorithms by mixing and matching contraction strategies.
Related