Prim's algorithm

Prim's algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized. The algorithm was discovered in 1930 by mathematician Vojtěch Jarník and later independently by computer scientist Robert C. Prim in 1957 and rediscovered by Edsger Dijkstra in 1959. Therefore it is sometimes called the DJP algorithm, the Jarník algorithm, or the Prim-Jarník algorithm.

Description

The algorithm continuously increases the size of a tree starting with a single vertex until it spans all the vertices.

• Input: A connected weighted graph with vertices V and edges E.
• Initialize: V_new = {x}, where x is an arbitrary node (starting point) from V, E_new= {}
• repeat until V_new=V:
  • Choose edge (u,v) from E with minimal weight such that u is in V_new and v is not (if there are multiple edges with the same weight, choose arbitrarily)
  • Add v to V_new, add (u,v) to E_new
• Output: V_new and E_new describe the minimal spanning tree

Time complexity

A simple implementation using an adjacency matrix graph representation and searching an array of weights to find the minimum weight edge to add requires O(V²) running time. Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can be shown to run in time which is O(E log V) where E is the number of edges and V is the number of vertices. Using a more sophisticated Fibonacci heap, this can be brought down to O(E + V log V), which is significantly faster when the graph is dense enough that E is Failed to parse (Missing texvc executable; please see math/README to configure.): \Omega (V log V).

Example

Pseudocode

Min-heap

Initialization

inputs: A graph, a function returning edge weights weight-function, and an initial vertex

initial placement of all vertices in the 'not yet seen' set, set initial vertex to be added to the tree, and place all vertices in a min-heap to allow for removal of the min distance from the minimum graph.

for each vertex in graph
   set min_distance of vertex to ∞
   set parent of vertex to null
   set minimum_adjacency_list of vertex to empty list
   set is_in_Q of vertex to true
set distance of initial vertex to zero
add to minimum-heap Q all vertices in graph.

Algorithm

In the algorithm description above,

nearest vertex is Q[0], now latest addition

fringe is v in Q where distance of v < ∞ after nearest vertex is removed

not seen is v in Q where distance of v = ∞ after nearest vertex is removed

The while loop will fail when remove minimum returns null. The adjacency list is set to allow a directional graph to be returned.

time complexity: V for loop, log(V) for the remove function

while latest_addition = remove minimum in Q
    set is_in_Q of latest_addition to false
    add latest_addition to (minimum_adjacency_list of (parent of latest_addition))
    add (parent of latest_addition) to (minimum_adjacency_list of latest_addition)

time complexity: E/V, the average number of vertices

    for each adjacent of latest_addition
    if (is_in_Q of adjacent) and (weight-function(latest_addition, adjacent) < min_distance of adjacent)
        set parent of adjacent to latest_addition
        set min_distance of adjacent to weight-function(latest_addition, adjacent)

time complexity: log(V), the height of the heap

        update adjacent in Q, order by min_distance

Proof of correctness

Let P be a connected, weighted graph. At every iteration of Prim's algorithm, an edge must be found that connects a vertex in a subgraph to a vertex outside the subgraph. Since P is connected, there will always be a path to every vertex. The output Y of Prim's algorithm is a tree, because the edge and vertex added to Y are connected. Let Y₁ be a minimum spanning tree of P. If Y₁=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge added during the construction of Y that is not in Y₁, and V be the set of vertices connected by the edges added before e. Then one endpoint of e is in V and the other is not. Since Y₁ is a spanning tree of P, there is a path in Y₁ joining the two endpoints. As one travels along the path, one must encounter an edge f joining a vertex in V to one that is not in V. Now, at the iteration when e was added to Y, f could also have been added and it would be added instead of e if its weight was less than e. Since f was not added, we conclude that

w(f) ≥ w(e).

Let Y₂ be the graph obtained by removing f and adding e from Y₁. It is easy to show that Y₂ is connected, has the same number of edges as Y₁, and the total weights of its edges is not larger than that of Y₁, therefore it is also a minimum spanning tree of P and it contains e and all the edges added before it during the construction of V. Repeat the steps above and we will eventually obtain a minimum spanning tree of P that is identical to Y₁. This shows Y is a minimum spanning tree.

Other algorithms for this problem include Kruskal's algorithm and Borůvka's algorithm.

References

• V. Jarník: O jistém problému minimálním [About a certain minimal problem], Práce Moravské Přírodovědecké Společnosti, 6, 1930, pp. 57-63. (in Czech)
• R. C. Prim: Shortest connection networks and some generalisations. In: Bell System Technical Journal, 36 (1957), pp. 1389–1401
• D. Cherition and R. E. Tarjan: Finding minimum spanning trees. In: SIAM Journal of Computing, 5 (Dec. 1976), pp. 724–741
• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.

External links

Wikimedia Commons has media related to:

Prim's Algorithm

• Analyze Prim's algorithm in an online Javascript IDE
• Minimum Spanning Tree Problem: Prim's Algorithm
• Create and Solve Mazes by Kruskal's and Prim's algorithms at cut-the-knot
• Animated example of Prim's algorithm
• Prim's Algorithm (Java Applet)
• Variation on Prims Algorithm to generate a shortest-route grid between a random set of points - written for Dark Basic Procs:Jarníkův algoritmus

de:Algorithmus von Prim es:Algoritmo de Prim fr:Algorithme de Prim ko:프림 알고리즘 id:Algoritma Prim it:Algoritmo di Prim he:האלגוריתם של פרים nl:Algoritme van Prim no:Prims algoritme pl:Algorytm Prima pt:Algoritmo de Prim ro:Algoritmul lui Prim ru:Алгоритм Прима sl:Primov algoritem sr:Примов алгоритам sv:Prims algoritm tr:Prim algoritması