Prim's Algorithm

Prim’s algorithm is a optimal greedy algorithm that is used to generate the minimum spanning tree (MST) of a weighted graph. It does so by picking the least weighted edge from the graph and exploits the cut property.

Negative edge weights allowed

Note that Prim’s algorithm can work on negative edge weights. In order to be correct, cost[v0] must be initialised to the lowest edge value. An easy way to do this is to set it to $-\infty$

Process §

1. Create an empty graph, $T$
2. Find the minimum edge $e=(u,v)$ where $u\in T$ and $v\in G\backslash T$ (See set difference)
   1. This can be done by using a set $Q$ to store all edges in $G$ that are not in $T$
3. Add $e$ to $T$
4. Repeat 2-3 $|V|-1$ times (since a tree must have $|V|-1$ edges)

Pseudocode §

Algorithm Prim(G: Graph):
	T ← Graph ADT
	For i from 1 to |V| - 1 do:
		Find the minimal weighted edge e = (u,v) where u in T and v in G but not T
		Add e to T
	End do
	Return T
End Algorithm 

A more detailed approach:

Algorithm Prim(G: Graph):

	Q <- Set of Nodes //Set of nodes that have not yet been added to T
	T <- Graph //Our final MST

	//Initialisation
	For each Node v in G do:
		cost[v] <- ∞
		prev[v] <- null
		Add v to Q
	End do

	While Q is not empty do:
		Remove a node u in Q with lowest cost[u]
		Add u to to T
		For all edges (u,v) with weight w do: //Not |E| but deg(u)
			If v in Q and w <= cost[v] then:
				cost[v] <- w
				prev[v] <- u
			End if
		End do
	End do

	//Edge reconstruction
	For each node v in T do:
		Add edge (v, prev[v]) to T
	End do
	
	Return T
	
End Algorithm 

Using the cost data structure avoids searching every edge for the minimum-cost edge, which can greatly reduce time in a dense graph

The way the lowest cost is obtained can greatly affect the final time complexity:

Nested Loop §

If Q is a simple array or linked list, then a for loop can be used to identify the minimum edge:

...

	Q <- Array

	While Q is not empty do:
		u <- First Node in Q
		For each Node n in Q do: //For loop to find min
			If cost[n] < cost[u] then:
				u <- n
			End if
		End do
		Add u to to T
		For each Edge (u,v) with weight w do:
			If v in Q and w <= cost[v] then:
				cost[v] <- w
				prev[v] <- u
			End if
		End do
	End do
	
...

Priority Queue §

A priority queue is ideal for finding the minimum edge, since a minimum priority queue will always return the cheapest edge efficiently:

Algorithm Prim(G: Graph):
	
	Q <- Min Priority Queue
	
	For each Node v in G do:
		...
		Enqeueue v to Q with priority ∞
	End do
	
	Pick a random v0 in G
	Update priority of v0 to -∞
	
	While Q is non-empty do:
		u <- Dequeue from Q
		For each edge (u,v) with weight w in G do:
			If v in Q and w < cost[v] then:
				cost[v] <- w
				prev[v] <- u
				Update v in Q with priority cost[w]
			End if
		End do
	End do

...

Manual Analysis §

One method of applying Prim’s algorithm manually is as follows:

1. Construct a table with the columns being nodes.
2. At each row, every entry has a value of $(\infty ,\text{nil})$, which specifies (distance,parent).
3. At row 1, set the lexicographical first node to have a distance of 0, i.e. $(0,nil)$
4. At row 2, add the lexicographical first node as the row name (specifying the nodes belonging to the final MST) and update the distance and parent values of any connecting edges.
5. Circle the edge with the minimum distance. If there is a tie, select with lexicographical order.
6. Add the node (looking at column name) to the tree in the next row.
7. Repeat steps 4-6, remembering to update nodes and only selecting minimum edges not belonging to the Tree. %%🖋 Edit in Excalidraw, and the light exported image%%

Time Complexity §

Naïve Implementation - Array for $Q$ and Adjacency Matrix Representation §

Basic Operation: Accessing a node (whether in $Q$ or in $G$)

The simplest way to implement Prim’s algorithm would be using an adjacency matrix for the graph and a linear data structure for $Q$. Then to obtain the minimum edge, a linear search can be used.

#todo

Case Scenario	Input Description	Growth Function	Asymptotic	Notes
Worst	$G$ is a complete graph (very dense)	#todo	$O(\Vert V{\Vert }^2)$	In a complete graph, $\Vert E\Vert =\Vert V\Vert (\Vert V\Vert -1)/2$, so fastest growing term is $\Vert V{\Vert }^2$
Average			$\Theta (\Vert V\Vert +\Vert E\Vert )$
Best	$G$ is a tree		$\Theta (\Vert V\Vert )$	In a tree, the number of edges is always $\Vert E\Vert =\Vert V\Vert -1$. $\Theta (\Vert V\Vert +\Vert V\Vert -1)=\Theta (\Vert V\Vert )$

Since every node must belong to $T$, we have $|V|$ iterations in the outermost loop (checking that $Q$ is non-empty). Then, inside we first do a loop through all node in $Q$ to find the min cost node. After that we do a search through all the edges of that min-cost node, which is the degree of the node:

$$O(|V|\cdot (|V|+\mathrm{deg}(v)))=O(|V{|}^2+|V|\cdot \mathrm{deg}(v))=O(|V{|}^2+|E|)=O(|V{|}^2)$$

Improved Version: Priority Queue (With Min Heap) for $Q$ and Adjacency List Representation §

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 §

Resources §

• Time complexity of Prim’s MST Algorithm