# Prim's AlgorithmEdit

Prim’s Algorithm is a fast algorithm for computing the MST (minimum spanning tree) of a connected graph.

## Algorithm description

Given a graph *G* described by a set of vertices *V* and edges between those vertices *E*:

- Pick a vertex
*s*arbitrarily from*V* - Create set
*X*, containing only*s*;*X*is the set of vertices spanned so far - Create empty tree
*T*;*T*is the partial MST that will be built up as the "while" loop executes - While
*X*!=*V*- Pick an edge
*e*between points*u*and*v*that is the cheapest edge of the graph, where*u*is in*X*and*v*is not in*X*(ie. crossing the boundary between the already-connected and not-yet-connected parts of the graph) - Add
*e*to*T* - Add
*v*to*X*

- Pick an edge

### Runtime of naïve implementation

In the naïve implementation:

*O(n)*iterations of the "while" loop (where*n*is the number of vertices)*O(m)*time per iteration (where*m*is the number of edges)*O(mn)*overall

### Performance improvements using the heap data structure

The heap data structure is good for doing repeated "extract min" operations, so if we use a heap to store the edges, with the keys being the edge costs, we can get our runtime down to *O(m log n)*.

Two invariants must be maintained:

- The heap contains the vertices of
*V*less those already pulled into*X*(ie.*V - X*) - For an element
*v*in the*V - X*heap, the key for*v*must be the cheapest edge*(u, v)*with*u*in*X*; if no such edge exists, then cost is*+infinity*

With those in place, doing an extract-min produces the next vertex *v* that is not in *X* and corresponding edge *(u, v)* crossing from *X* to *V - X* that should be added to *X* and *T* respectively.

In order to maintain the second invariant, we do the following when adding *v* to *X*:

- For each edge
*(v, w)*in*E*- If
*w*is in*V - X*- Delete
*w*from the heap (requires some additional book-keeping, so that we know the position of each vertex within the heap) - Recompute the key for
*w*to be the lesser of its former value or cost of the edge*(v, w)* - Reinsert
*w*into the heap

- Delete

- If

### Runtime of heap-based implementation

- Heap operations dominate:
*n - 1*inserts during preprocessing*n - 1*"extract-min" operations (one for each iteration of "while" loop)*m*delete + insert operations (one for each edge, as its first endpoint gets pulled into*X*)

So we’re looking at *O(m)* for heap operations (as *m >= n - 1* in a connected graph), and an overall runtime of *O(m log n*).

## Notes

Unlike Kruskal’s Algorithm, Prim’s Algorithm only works on connected graphs.