Minimum Spanning Trees

Explain Prim’s and Kruskal’s minimum spanning tree algorithms and give similarities and differences.

Prim’s Algorithm

Prim’s works by starting at any vertex, and finding the minimum edge weight between a tree and a non-tree vertex. It will then add that minimum edge and vertex to the minimum spanning tree.

Kruskal’s Algorithm

Kruskal’s first sorts all the edges of a graph by weight, and inserts them into a priority queue. It then loops through the priority queue, getting the edge with the lowest weight, and checks if it will create a cycle in the minimum spanning tree. If it would not, it will add that edge to the minimum spanning tree, and merge the two vertices.

Analysis

  • Kruskal’s offers a little bit of control over the minimum spanning tree as it always begins at the same spot, however, because Prim’s starts at an arbitrary vertex, it is a bit harder to control.
  • Both algorithms can be implemented using a priority queue, however, Kruskal’s also makes use of disjoint sets and a Union-Find class.
  • The default time complexity of Prim’s algorithm is n iterations each looping through all possible edges m, making the time complexity O(nm), however, this can be improved to O(n²) when using a priority queue. On the other hand, the time complexity of Kruskal’s is simply O(E log(V)), E being edges, and V being vertices.
  • Prim’s algorithm performs best when the given graph is very dense, whereas Kruskal’s performs best when the given graph is sparse.