= Prim's Algorithm =

MST-Prims$$(G(V,E),w(e \in 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)$$.