About Prim's algorithm

And yeah, you guessed it right, I've studied the Prim's algorithm too, and am gonna talk trash 'bout it. Biatch. I mean it's cool since it's my fucking blog, I can say anything. Cool. Cool cool cool.

Coming back to the topic.
How does the Prim's algorithm satisfy the generic MST method ?:

Well, the set $A$ basically contains a subset of the final MST built. We can say that $A$ respects a cut, $(S,V-S)$, in which set $S$ contains all the vertices that are joined via the edges in $A$. Prim's algorithm finds a light edge that crosses  this cut, and by corollary 23.2, we can say that this light edge is safe.

Pseudo-code:

     MST-PRIM$(G,w,r)$

1. for each $u \in G.V$
2.       $u.key = \infty $
3.       $u.\pi = NIL$
4. $r.key = 0 $
5. $Q = G.V$
6. while $Q \neq \phi$
7.       $u =$ EXTRACT-MIN$(Q)$ 
8.       for each $v \in G.Adj[u]$
9.             if $v \in Q$ and $w(u,v)<v.key$
10.                   $v.\pi = u$
11.                   $v.key = w(u,v)$

Explanation:

Basically, we have this tree, living inside $A$ (thriving...etc.). We have this min-priority queue $Q$ which has all the vertices that are not in the set of vertices joined by the edges in $A$. Each vertex maintains the distance from the tree built. Therefore initially it's $\infty$ for all vertices, but the root. Now, we keep on adding those vertices to the tree that are the nearest to it (using the EXTRACT-MIN operation), until no vertex is left, ( that is, $Q$ becomes empty).

Implementation:

The priority queue is implemented using min-heaps. If we use Fibonacci heaps, we can get a better running time.

Running time:

EXTRACT-MIN runs in $O(lg V)$.
Updating keys in the priority queue takes $O(lg V)$  in min-heap , and $O(1)$ time in a fibonacci heaps. (that is, the DECREASE-KEY operation)

The while loop runs in $O(E)$ time and the inner loop in a total of $O(E)$ time. Thus a total of $O(E lgV+VlgV) = O(ElgV)$ time, if we use min-heaps, and $O(E+VlgV)$ time if we use fibonacci heaps.