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)$
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.
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)$
- for each $u \in G.V$
- $u.key = \infty $
- $u.\pi = NIL$
- $r.key = 0 $
- $Q = G.V$
- while $Q \neq \phi$
- $u =$ EXTRACT-MIN$(Q)$
- for each $v \in G.Adj[u]$
- if $v \in Q$ and $w(u,v)<v.key$
- $v.\pi = u$
- $v.key = w(u,v)$
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.
