Prim's Algorithm

• MST-Prims(G(V,E),w(e∈E),r) // 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: O(V+VlogV+ElogV), which reduces to:
  • O(ElogV)
  However this can be increased by using a fibonacci heap where Extract-Min in O(log v) and Decrease-Key in O(1), thus we can reduce line 11, and get a running time of
  • O(E+VlogV)