Jarník’s (“Prim’s”) Algorithm

Introduction to Jarník’s (“Prim’s”) algorithm

The next oldest minimum spanning tree algorithm was first described by the Czech mathematician Vojtěch Jarník in a 1929 letter to Borůvka; Jarník published his discovery the following year. The algorithm was independently rediscovered by Joseph Kruskal in 1956, (arguably) by Robert Prim in 1957, by Harry Loberman and Arnold Weinberger in 1957, and finally by Edsger Dijkstra in 1958. Prim, Lobermand and Weinberger, and Dijkstra all (eventually) knew of and even cited Kruskal’s paper, but since Kruskal also described two other minimum spanning tree algorithms in the same paper, this algorithm is usually called “Prim’s algorithm,” or sometimes “the Prim/Dijkstra algorithm,” even though by 1958 Dijkstra already had another algorithm (inappropriately) named after him.

Methodology

In Jarník’s algorithm, the intermediate forest $F$ has only one nontrivial component $T$; all the other components are isolated vertices. Initially, $T$ consists of a single arbitrary vertex of the graph. The algorithm repeats the following step until $T$ spans the whole graph:

• $Jarník$: Repeatedly add $T’s$ safe edge to $T$.

To implement Jarník’s algorithm, we keep all the edges adjacent to $T$ in a priority queue. When we pull the minimum-weight edge out of the priority queue, we first check whether both of its endpoints are in $T$ . If not, we add the edge to $T$ and then add the new neighboring edges to the priority queue. In other words, Jarník’s algorithm is a variant of best-first search algortihm. If we implement the underlying priority queue using a standard binary heap, Jarník’s algorithm runs in $O(E\log E) = O(E\log V)$ time.

Improving Jarník’s algorithm

We can improve Jarník’s algorithm using a more complex priority queue data structure called a Fibonacci heap, first described by Michael Fredman and Robert Tarjan in 1984. Just like binary heaps, Fibonacci heaps support the standard priority queue operations $Insert$, $ExtractMin$, and $DecreaseKey$ ...