Prim's Algorithm

#programming #algorithms

See also : Kruskal's Algorithm

Question

Find the Minimum Spanning Tree of a connected, undirected, weighted graph.

What it mean

Imagine an undirected, connected graph, you are given it's vertices and it's weighted edges.

The goal is to :

Connect all vertices using some of the edges such that

1. The graph is still connected.
2. There are no cycles (ie, it's a tree)
3. The total sum of edge weights is minimum

Mental model

Imagine a collection of multiple cities, and a road network that connects them, with each road having a cost.

What we require is a way to connect all cities using the least total cost, without building unnecessary roads.

Spanning : Connects all vertices
Tree : Without a single cycle.
Minimum : Total cost is minimized.

Approach

We start from any node, and then attempt to find the minimum weight edge that connects this node to any other node not currently in the MST.

This is a greedy approach

For this, we require the following

• $\mathrm{key}[\mathrm{v}]⟹$ minimum weight edge connecting node $v$ to the tree.
• $\mathrm{parent}[\mathrm{v}]⟹$ which node connects it
• $\mathrm{inMST}[\mathrm{v}]⟹$ whether node is in the MST.
• min-heap $⟹$ to extract the minimum weighted edge outgoing from node.

Intuition

We are always picking

The lightest edge crossing the cut between MST-set and non-MST-set.

This is also why greedy works

So essentially, we have a "visited" region:

• At every step we expand this region by choosing the outgoing edge with the minimum weight.

This implies that any cheaper connection, that could've made our solution wrong, is guaranteed to have been picked earlier and considered. (Also a reason why greedy works)

Psuedo-code

pick start node // say node=0;
key[0] = 0; 
key[everything else] = infinity; 
push(key[0], 0) into min-heap;
while heap is not empty:
	key, node = extract min from min-heap
	mark node as inMST
	for each neighbour v of node:
		if v not in MST and weight(u,v) < key[v]:
			key[v] = weight(u,v);
			parent[v] = u
			push(key[v], v) to heap
Repeat till all vertices are covered. 

Time complexity

Naive : Adj matrix $⟹O(V^2)$

• Find min key $⟹O(V)$
• Repeated $V$ times, $⟹O(V^2)$
• Updating neighbours $⟹O(V)$

TOTAL : $O(V^2)$

Using Binary heap + adjacent list

• Best case : $O(E\log V)$, Graph is already an MST or consists of disconnected components
• Average case : $O((V+E)\log V)\approx O(E\log V)$
• Worst case : $O((V+E)\log V)$