Prim's algorithm

In graph theory, Prim’s algorithm is a solution to the minimum spanning tree problem, i.e., given a positive weighted connected undirected graph $G=(V,E)$, it finds an MST such that the edges have the minimum weight. It does this by using a greedy approach (much like Dijkstra’s algorithm).

Implementation and analysis

The pseudocode for Prim’s is given by:

Prim-MST(G, w, r):
	insert every vertex in Q with infinity
	while (Q != \empty)
		u = Extract-Min(Q)
		foreach v adjacent to u by edge (u, v)
			if w(u, v) < key(v)
				Decrease-Key(v, w(u, v))
				π(i) = u

Step-by-step, Prim’s algorithm:

• Sets the key of each vertex to $\infty$, except for the root $r$ which is set to 0 to indicate that it’s been processed.
• Set the parent of each vertex to NIL, and insert each vertex into a min-priority queue $Q$.
• Then, the algorithm begins a loop.
  • It identifies the lowest weight edge $u$ (i.e., a light edge) that crosses the cut $(V-Q,Q)$, then removes it from the priority queue and add it to the set $V-Q$ of vertices in the tree.
  • The for loop updates the key and parent attributes of every vertex $v$ adjacent to $u$ but not in the tree, which maintains the algorithm’s loop invariant,
  • Then, if the edge weight is less than the key of $v$, it is overwritten with the edge weight, and Decrease-Key updates the key value in the priority queue.

The time complexity is primarily dominated by the while loop and its contents. The outer loop runs in $\mathcal{O}(V)$ time, Extract-Min takes $\mathcal{O}(\log V)$ (assuming a binary heap), the for loop that updates the key/parent attributes, and Decrease-Key also takes $\mathcal{O}(\log V)$. So the total time complexity is $\mathcal{O}(V\log V+E\log V)=\mathcal{O}(E\log V)$, which is asymptotically the same as Kruskal’s algorithm.

Tutorial

ATaC $\exists$ MST $T$ such that $e\notin T$. $T\cup \{e\}$ gives us a cycle $f\in$ cycle, $f\ne e$, $T=T\cup \{e\}\backslash \{f\}$, which is spanning $w(T^{\prime })=w(T)+w(e)-w(f)$ contradiction somewhere let $e=(u,v)$ be max edge weight and $\exists p$ path connecting $(u,v)$ where $e\notin p$ ATaC $\exists$ MST $T$ such that $e\in T$ let $f$ be an edge on path $p$ that is not in $T$ i.e., u → v via e and u ← v via p consider $T\cup \{f\}$ which must have a cycle, and cycle includes $e$ by how $f$ is defined $T^{\prime }=T\cup \{f\}\backslash \{e\}$ $w(T^{\prime })<w(T)$ so contradiction

looks pretty similar to greedy proofs