Résumé: We study the expected performance of Prim's minimum spanning tree (MST) 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+nlognlog(2m/n)) time. Note that O(m+nlognlog(2m/n))=O(m) when m=(nlognloglogn). We extend this result to show that the same expected run times apply even when an adversary can select the weights of m/logn edges and the possible weights of the remaining edges (which are then randomly assigned).

Langue: Anglais