Prim's Algorithm

Prim’s algorithm is a greedy algorithm used to generate the MST of a weighted, undirected graph.

Pseudocode §

Get the actual pseudocode

Algorithm Prim(Graph, optional start):
	MST ← Graph ADT
	Add start node to T (or random node if start isn't specified)
	While T.vertices = G.vertices do: #O(|V|)
		Get all outgoing edges from T #O(|E|)
		Select cheapest edge e (u-v), where u is in T
		If v in T, discard it
		Add e to T
	End do
	Return T
End Algorithm 

Complexity §

Time Complexity: $O(|V||E|)$ §

$O(|V|)$ for outer while loop x $O(|E|)$ for getting all outgoing edges (inner loop)

Given a complete graph, where $|E|$ = $\frac{|V|(|V|-1)}{2}$, Prim’s takes $O(n^3)$ = $O(|V||E|)$ =$O(|V{|}^3)$

Proof Of Correctness §

Via Loop Invariants

Loop Invariant: The subtree T generated by Prim’s is a subset of the true MST (T*) for all iterations

Initialization: Before the loop, T contains no edges. Therefore, it can be trivially proven that T is a subset of T*, as an empty set is a subset of all sets:

Maintenance: For each iteration, Prim’s only selects the cheapest edge, , and does not permit it to cause an cycles. According to the cut property, all MSTs contain e, therefore

Termination: The loop terminates only when all the nodes from T* are in T. Since, for each iteration, T is a subset of T*, during the termination of loop T = T*.

Implementation §

Prim.py