Given an *undirected weighted graph*, a minimum spanning tree (MST) is a subset of the edges of the graph which *form a tree* and have the *minimum total edge weight*. For a MST to exist, the graph must be *connected *(that is, every pair of nodes must be reachable from each other)*.*

Prim's algorithm build's the minimum spanning tree **one vertex at a time**. To see what that means, watch the following video.

# Video with step-by-step example

# Algorithm steps

- Start at an arbitrary node. Mark the node
*visited*. Mark all other nodes*unvisited*. - While there is an unvisited node
- Consider all edges which connect a
*visited*node to an*unvisited*node. Out of these edges, pick the one with the minimum weight. - Mark the
*unvisited*node corresponding to the edge*visited*. Add edge to minimum spanning tree. - Done!

# Pseudo-code

define prims_algorithm(graph):# initializationunvisited = set(all nodes in graph)heap = empty heapMST = empty set# start at an arbitrary nodesource = choose node at randomunvisited.remove(source) # mark visitedfor neighbor of source:# add edge to heap with priority=edge weightheap.insert_with_priority(edge_weight(source, neighbor), (source, neighbor))# while there is an unvisited nodewhile not unvisited.empty():# if heap is empty, graph is disconnectedif heap.empty(): return INFINITY# get minimum-weight edge to an unvisited node from heap# (note: all edges in heap have at-least one end = visited node)edge_weight, (previous, node) = heap.pop()if node not in unvisited: continue # already visited# found new reachable node. mark visited and update MSTunvisited.remove(node)MST.add((previous, node))# add all edges from this node to the heapfor neighbor of node:# add edge to heap with priority=edge weightheap.insert_with_priority(edge_weight(node, neighbor), (node, neighbor))return MST

# Run-time analysis

Given a graph with n nodes and m edges, Prim's algorithm has a run-time of O(m \log m). Since m \leq n^2, this is also O(m \log n). The most expensive operation is heap inserts and heap pops, and we do each operation m times (once per edge).

# Correctness of Prim's algorithm

## The cut property

The main idea behind both Prim's algorithm and Kruskal's algorithm is the cut property.

Consider any subset S of all vertices V of the graph. Consider all edges going from a vertex in S to a vertex outside S. The cut property states that, if e is the edge with minimum weight among all these edges, then e must be part of the minimum spanning tree.

**Proof of cut property**: The proof is quite simple. Assume the contrary, that is, the MST of the graph does not include e. Since the minimum spanning tree spans all vertices, it has at-least one edge e' going from S to outside S. If this edge is replaced by e, we get a spanning tree with lesser weight. This is a contradiction, since the original tree was a *minimum* spanning tree.

## Correctness of Prim's algorithm

In Prim's algorithm, in each step, we consider a cut and choose the minimum weight edge crossing the cut. Each of these edges must be part of the MST, as proved above.