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 Dijkstra in 1959. Therefore it is sometimes called the DJP algorithm or Jarnik algorithm. A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...
The minimum spanning tree of a planar graph. ...
This article just presents the basic definitions. ...
A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
In geometry, a vertex (Latin: whirl, whirlpool; plural vertices) is a corner of a polygon (where two sides meet) or of a polyhedron (where three or more faces and an equal number of edges meet). ...
A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...
Year 1930 (MCMXXX) was a common year starting on Wednesday (link is to a full 1930 calendar). ...
VojtÄ›ch JarnÃk (December 22, 1897  September 22, 1970) was a Czech mathematician. ...
Computer science (informally: CS or compsci) is, in its most general sense, the study of computation and information processing, both in hardware and in software. ...
Robert Clay Prim (born 1921 in Sweetwater, Texas) is an American mathemetician and computer scientist. ...
Year 1957 (MCMLVII) was a common year starting on Tuesday of the Gregorian calendar. ...
Edsger Dijkstra Edsger Wybe Dijkstra (Rotterdam, May 11, 1930 â€“ Nuenen, August 6, 2002; IPA: ) was a Dutch computer scientist. ...
Year 1959 (MCMLIX) was a common year starting on Thursday of the Gregorian calendar. ...
Description
 create a tree containing a single vertex, chosen arbitrarily from the graph
 create a set (the 'not yet seen' vertices) containing all other vertices in the graph
 create a set (the 'fringe' vertices) that is initially empty
 loop (number of vertices  1) times
 move any vertices that are in the not yet seen set and that are directly connected to the last node added into the fringe set
 for each vertex in the fringe set, determine if an edge connects it to the last node added and if so, if that edge has smaller weight than the previous edge that connected that vertex to the current tree, record this new edge through the last node added as the best route into the current tree.
 select the edge with minimum weight that connects a vertex in the fringe set to a vertex in the current tree
 add that edge to the tree and move the fringe vertex at the end of the edge from the fringe set to the current tree vertices
 update the last node added to be the fringe vertex just added
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^2) 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(Elog 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 + Vlog V), which is significantly faster when the graph is dense enough that E is Ω(Vlog V). In mathematics and computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the n Ã— n matrix where the nondiagonal entry is the number of edges from vertex i to vertex j, and the diagonal entry is either twice the number of loops...
Example of a complete binary max heap. ...
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ...
In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ...
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ...
Image File history File links Information_icon. ...
In mathematics and computer science, the adjacency matrix of a finite directed or undirected graph G on n vertices is the n Ã— n matrix where the nondiagonal entry is the number of edges from vertex i to vertex j, and the diagonal entry is either twice the number of loops...
The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
Example of a complete binary max heap. ...
In graph theory, an adjacency list is the representation of all edges or arcs in a graph as a list. ...
The Big O notation is a mathematical notation used to describe the asymptotic behavior of functions. ...
In computer science, a Fibonacci heap is a data structure similar to a binomial heap but with a better amortized running time. ...
Example Image  Description  Not seen  Fringe  Solution set 
 This is our original weighted graph. This is not a tree because the definition of a tree requires that there are no circuits and this diagram contains circuits. A more correct name for this diagram would be a graph or a network. The numbers near the arcs indicate their weight. None of the arcs are highlighted, and vertex D has been arbitrarily chosen as a starting point.  C, G  A, B, E, F  D 
 The second chosen vertex is the vertex nearest to D: A is 5 away, B is 9, E is 15, and F is 6. Of these, 5 is the smallest, so we highlight the vertex A and the arc DA.  C, G  B, E, F  A, D 
 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. 6 is the smallest, so we highlight the vertex F and the arc DF.  C  B, E, G  A, D, F 
 The algorithm carries on as above. Vertex B, which is 7 away from A, is highlighted. Here, the arc DB is highlighted in red, because both vertex B and vertex D have been highlighted, so it cannot be used.  null  C, E, G  A, D, F, B 
 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 EB. Two other arcs have been highlighted in red, as both their joining vertices have been used.  null  C, G  A, D, F, B, E 
 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. The arc BC is also highlighted in red.  null  G  A, D, F, B, E, C 
 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 highlighted, the minimum spanning tree is shown in green. In this case, it has weight 39.  null  null  A, D, F, B, E, C, G  Image File history File links Prim_Algorithm_0. ...
Image File history File links Prim_Algorithm_1. ...
Image File history File links Prim_Algorithm_2. ...
Image File history File links Prim_Algorithm_3. ...
Image File history File links Prim_Algorithm_4. ...
Image File history File links Prim_Algorithm_5. ...
Image File history File links Prim_Algorithm_6. ...
The minimum spanning tree of a planar graph. ...
Pseudocode Minheap  Initialization
 inputs: A graph, a function returning edge weights weightfunction, 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 minheap 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 nil 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 minimumheap 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. KK Null, a Japanese musician Null, a special value in computer programming. ...
 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 (weightfunction(latest_addition, adjacent) < min_distance of adjacent) set parent of adjacent to latest_addition set min_distance of adjacent to weightfunction(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_{1} be a minimum spanning tree of P. If Y_{1}=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_{1}, 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_{1} is a spanning tree of P, there is a path in Y_{1} 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 A labeled tree with 6 vertices and 5 edges In graph theory, a tree is a graph in which any two vertices are connected by exactly one path. ...
 w(f) ≥ w(e).
Let Y_{2} be the graph obtained by removing f and adding e from Y_{1}. It is easy to show that Y_{2} is connected, has the same number of edges as Y_{1}, and the total weights of its edges is not larger than that of Y_{1}, 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. Kruskals algorithm is an algorithm in graph theory that finds a minimum spanning tree for a connected weighted graph. ...
BorÅ¯vkas algorithm is an algorithm for finding minimum spanning trees. ...
References  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 McGrawHill, 2001. ISBN 0262032937. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.
Robert Endre Tarjan (born April 30, 1948 in Pomona, California) is a renowned computer scientist. ...
Thomas H. Cormen is the coauthor of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ...
Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ...
Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ...
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ...
Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...
External links  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 cuttheknot
 Animated example of Prim's algorithm
 Prim's Algorithm (Java Applet)
