The expected complexity of Prim's minimum spanning tree algorithm

摘要

We study the expected performance of Prim's minimum spanning tree (MS) algorithm implemented using ordinary heaps. We show that this implementation runs in linear or almost linear expected time on a wide range of graphs. This helps to explain Why Prim's algorithm often beats MST algorithms which have better worst-case run times. Specifically, we show that if we start with any n node m edge graph and randomly permute its edge weights, then Prim's algorithm runs in expected O(m+n log n log (2m)) time. Note that O(m+n log n log (2m))=O(m) when m= Ω(n log n log log n).