Prim’s algorithm

This solves the MST problem using a method similar to Dijkstra’s algorithm. It will use a Priority queue to do this.

Algorithm

Prim's(G,w):
	Input: undirected graph G=(V,E) with weights w(e).
	Output: MST defined by the array prev
for all u in V
	cost(u) = inf
	prev(u) = nil
Pick any initial node u_0
cost(u_0) = 0
 
H = makequeue(V)
while H is not empty:
	v = deletemin(H)
	for each {v,z} in E:
		if cost(z) > w(v,z):
			cost(z) = w(v,z)
			prev(z) = v
			decreasekey(H,z)
output prev

Correctness

Note that functionally Prim’s algorithm is slowly building a tree using the closes vertex to the currently constructed tree that is not already in it.

We prove by induction on the size of that this must be a subset of some MST.

Base case

.

Note there must be an MST and . Therefore and we have shown it true for the base case.

Induction case

Suppose for some MST .

Suppose we find the next closest vertex . I.e. There is some minimum weight edge the cut edges of .

Therefore by the cut property is contained in some MST .

This proves the induction case and we have that is always a subset of some MST.

Conclusion

As the algorithm runs until each vertex is added to the tree . is a spanning tree which is a subset of a MST. Therefore is an MST in its own right.

Run time

Initialisation takes steps.

To fetch the key takes time from Priority queue data structure. This is executed times so takes .

We iterate over each edge twice and for each iteration we might have to call decreasekey which takes time from Priority queue implementation. So this takes .

All together this takes .