FACTOID # 11: Oklahoma has the highest rate of women in State or Federal correctional facilities.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > 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 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. ...

Contents

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

Minimum edge weight data structure Time complexity (total)
adjacency matrix, searching V^2
binary heap (as in pseudocode below) and adjacency list O((V + E) log(V)) = E log(V)
Fibonacci heap and adjacency list 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(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

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 toset 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 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. 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 (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 Y1 be a minimum spanning tree of P. If Y1=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 Y1, 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 Y1 is a spanning tree of P, there is a path in Y1 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 Y2 be the graph obtained by removing f and adding e from Y1. It is easy to show that Y2 is connected, has the same number of edges as Y1, and the total weights of its edges is not larger than that of Y1, 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

Robert Endre Tarjan (born April 30, 1948 in Pomona, California) is a renowned computer scientist. ... Thomas H. Cormen is the co-author 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

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)

  Results from FactBites:
 
MATLAB Central File Exchange - Prims Algorithm (439 words)
In the mathematical field of graph theory, a spanning tree of a connected, undirected graph is a tree which includes every vertex of that graph.
Prim's algorithm builds a tree while having the graph connected at all times.
Prim's algorithm maintains two lists, EV which is the vertices already in the tree, and E, the list of edges that makes up the spanning tree.
Prim Algorithm. (331 words)
n every execution of the Prim Algorithm a new peak will be connected to the T tree,not always with their numbering order, for example the V
peak.The corresponding pointer of the newly connected peak will be deleted from P set and will be inserted to the O set.When all peaks are connected there will be O={1,...n} and P=0.This of course means the end of the algorithm.
ou can also see an example of prim algorithm using the
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m