Algorithms For Dummies

 Exploring the World of Graphs

The example uses a priority queue based on a binary heap for the heavy job of 

picking up the shortest edges, but there are even faster data structures, such as 

the Fibonacci heap, which can produce faster results when the heap contains many 

edges. Using a Fibonacci heap, the running complexity of Prim’s algorithm can 

mutate to O(E +V*log(V)), which is clearly advantageous if you have a lot of edges 

(the E component is now summed instead of multiplied) compared to the previous 

reported running time O(E*log(V)).

Kruskal’s algorithm doesn’t much need a priority queue (even though one of the 

examples uses one) because the enumeration and sorting of edges happens just 

once at the beginning of the process. Being based on simpler data structures that 

work through the sorted edges, it’s the ideal candidate for regular, sparse graphs 

with fewer edges.