Algorithms‎ > ‎Graphs‎ > ‎Minimum Spanning Trees‎ > ‎

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 developed in 1930 by Czech mathematician Vojtech Jarnik 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.
 

Algorithm

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: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}
  • Repeat until Vnew = V:

    • Choose edge (u,v) with minimal weight such that u is in Vnew and v is not (if there are multiple edges with the same weight, choose arbitrarily but consistently)
    • Add v to Vnew, add (u, v) to Enew
  • Output: Vnew and Enew describe a minimal spanning tree
    •  
      Example
      Image Description
      This is our original weighted graph. The numbers near the edges indicate their weight.
      Vertex D has been arbitrarily chosen as a starting point. Vertices A, B, E and F are connected to D through a single edge. A is the vertex nearest to D and will be chosen as the second vertex along with the edge AD.
      The next vertex chosen is the vertex nearest to either D or A. B is 9 away from D and 7 away from A, E is 15, and F is 6. F is the smallest distance away, so we highlight the vertex F and the arc DF.
      The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted.
      In this case, we can choose between C, E, and G. C is 8 away from B, E is 7 away from B, and G is 11 away from F. E is nearest, so we highlight the vertex E and the arc BE.
      Here, the only vertices available are C and G. C is 5 away from E, and G is 9 away from E. C is chosen, so it is highlighted along with the arc EC.
      Vertex G is the only remaining vertex. It is 11 away from F, and 9 away from E. E is nearer, so we highlight it and the arc EG.
      Now all the vertices have been selected and the minimum spanning tree is shown in green. In this case, it has weight 39.
       
       
      Time complexity
      Minimum edge weight data structure Time complexity (total)
      adjacency matrix, searching O(V2)
      binary heap (as in pseudocode below) and adjacency list O((V + E) log(V)) = O(E log(V))
      Fibonacci heap and adjacency list O(E + V log(V))

      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(V2) running time. Using a simple binary heap data structure and an adjacency list representation, Prim's algorithm can be shown to run in time 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 ω(V).

      Comments