Assume that in a network of computers any two computers can

Assume that in a network of computers any two computers can be link a cost estimate for each possible link, should Algorithm 4.1 (Prim\'s algorithm) or Algorithm 4.2 (Kruskal\'s algorithm) be used? Justify your answer 10.

Solution

Use Prim\'s algorithm when you have a graph with lots of edges.

Kruskal’s minimum spanning tree algorithm starts with the empty graph and then selects edges from E according to the following rule.

Repeatedly add the next lightest edge that doesn’t produce a cycle.

The correctness of Kruskal’s method follows from a certain cut property, which is general
enough to also justify a whole slew of other minimum spanning tree algorithms.