Jarník's algorithm
Introduction
Jarník's algorithm, also known as Prim's algorithm, is a computer algorithm that is used to find a minimum spanning tree for a connected, undirected graph. This algorithm operates by building this tree one vertex at a time, from an arbitrary starting vertex, at each step adding the cheapest possible connection from the tree to another vertex.
History
The algorithm was developed by Czech mathematician Vojtěch Jarník in 1930 and later independently rediscovered by computer scientist Robert C. Prim in 1957. It was also independently developed by Edsger W. Dijkstra in 1959. Despite its multiple discoveries, it is most commonly referred to as Prim's algorithm in the field of computer science.
Algorithm Description
Jarník's algorithm starts with an arbitrary node and grows the minimum spanning tree from that node by always adding the shortest edge that connects a node in the tree to a node outside of the tree. The algorithm maintains a priority queue of edges that are proposed to connect the two sets of nodes, and it always chooses the shortest edge from this queue. The algorithm continues until all nodes are included in the tree.
Mathematical Formulation
The algorithm can be expressed in more formal mathematical terms as follows:
Let G = (V, E) be a connected, undirected graph where V is the set of vertices and E is the set of edges. Each edge has a weight w(e) associated with it. The algorithm maintains a tree T that starts with an arbitrary vertex v. At each step, the algorithm adds to T the edge e that has minimum weight among all edges that connect T to V - T.
Pseudocode
The algorithm can be implemented using the following pseudocode:
``` function Jarnik(G, w, r)
for each u in V[G]
key[u] = ∞
π[u] = NIL
key[r] = 0
Q = V[G]
while Q ≠ Ø
u = Extract-Min(Q)
for each v in Adj[u]
if v in Q and w(u, v) < key[v]
π[v] = u
key[v] = w(u, v)
```
In this pseudocode, G is the graph, w is the weight function, r is the root of the tree, V[G] is the set of vertices in G, key[u] is the minimum weight of any edge connecting vertex u to a vertex in the tree, π[u] is the parent of u in the tree, and Adj[u] is the set of vertices adjacent to u.
Time Complexity
The time complexity of Jarník's algorithm depends on the data structures used for the graph and the priority queue. If the graph is represented by an adjacency matrix and the priority queue is implemented as a simple linear array, the time complexity is O(V^2), where V is the number of vertices in the graph. If the graph is represented by an adjacency list and the priority queue is implemented as a binary heap, the time complexity is O(E log V), where E is the number of edges in the graph.
Applications
Jarník's algorithm has numerous applications in network design, including computer network design, circuit design, and transportation network planning. It is also used in clustering algorithms in machine learning, in the design of minimum-cost spanning trees in telecommunications, and in the generation of mazes.