Prim’s Algorithm
It is a minimum spanning tree algorithm.
It scales well, fast with dense graphs.
It has a of with binary heap and with Fibonacci heap.
It works like this:
- Choose any node.
- Choose nearest node that is not included in the spanning subtree formed so far.
- Repeat step 2 until all nodes are included in the subtree.
Pseudo-Code
Algorithm 4. PrimsMST(G=(V,E))
Input: G- a weighted graph (V- vertices, E- Edges)
1) Let x be a random node from V
2) Let Vnew = {x}
3) Let Enew = {}
4) While Vnew V
5) Choose an edge (u,v) with minimal weight,
such that u Vnew and v Vnew
6) Vnew = Vnew {v}
7) Enew = Enew {(u,v)}
8) Wend
Output: Gnew = (Vnew,Enew)
Example
