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.
- 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.
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
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).
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.
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.