# Prim's Algorithm
> In Prim's algorithm, the set $A$ forms a single tree. The safe edge added to
> $A$ is always a lowest-weight edge connecting the tree to a vertex not in the
> tree.
- Example of a [[greedy]] algorithm, each edge added added contributes minimum
to the weight of tree.
- Maintains a [[priority-queue|min-priority queue]] of all vertices not in the
tree, based on `key`, i.e. the minimum weight edge connecting the vertex to
the tree.
```
MST-PRIM(Q, w, r)
for each vertex u in G.V
u.key = Inf
u.pi = NIL
r.key = 0
Q = {}
for each vertex u in G.V
INSERT(Q, u)
while Q != {}
u = EXTRACT-MIN(Q) // add u to the tree
for each vertex v in G.Adj[u] // update keys of u's non-tree neighbors
if v in Q and w(u, v) < v.key
v.pi = u
v.key = w(u, v)
DECREASE-KEY(Q, v, w(u, v))
```
- $O(E\lg V)$ with binary [[heap]]
- $O(E + V\lg V)$ time with [[fibonacci-heap|Fibonacci heap]], so that `INSERT`
and `DECREASE-KEY` takes $O(1)$ time.