Prim's Algorithm

MST-Prims // G-graph, w-weight function, r is where we start

   1. for each u in V                           O(V)
   2.   key[u]=infinity;                                O(1)
   3.   p[u]=Nil                                        O(1)
   4. key[r]=0 //decrease key                   O(1)
   5. Insert V into Q //a min priority queue    O(V)
   6. While Q!=empty set;                       O(V)
   7.   u=Extract-Min(Q)                                O(logV)
   8.   for each v Adj[u]                       2E times =O(E) We analyze this seperate
   9.      if v in Q and w(u,v)<key[v]          O(1)
   10.         p[v]=u                                   O(1)
   11.         key[v]=w(u,v) //decrease key operation   O(logV)

Running Time: , which reduces to: However this can be increased by using a fibonacci heap where Extract-Min in and Decrease-Key in , thus we can reduce line 11, and get a running time of .