Prim's algorithm

From Wikipedia, the free encyclopedia

This article appears to contradict itself.
Please see the discussion on the talk page.

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. If the graph is not connected, then it will only find a minimum spanning tree for one of the connected components. 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.

It works as follows:

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 fring set to the current tree vertices
- update the last node added to be the fringe vertex just added

Only |V|-1, where |V| is the number of vertices in the graph, iterations are required. A tree connecting |V| vertices only requires |V|-1 edges (anymore causes a cycle into the subgraph, making it no longer a tree) and each iteration of the algorithm as described above pulls in exactly one edge.

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

1 Example
2 Pseudocode
3 Proof of correctness
4 References
5 External links

[edit] Example

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

[edit] Pseudocode

 Minimum-Spanning-Tree-by-Prim(G, weight-function, source)
 1  for each vertex u in graph G
 2    set key of u to ∞
 3    set parent of u to nil
 4  set key of source vertex to zero
 5  enqueue to minimum-heap Q all vertices in graph G. 
 6  while Q is not empty
 7    extract vertex u from Q // u is the vertex with the lowest key that is in Q
 8    for each adjacent vertex v of u do
 9      if (v is still in Q) and (weight-function(u, v) < key of v) then
10        set u to be parent of v  // in minimum-spanning-tree
11        update v's key to equal weight-function(u, v)

This pseudocode is essentially the same as the algorithm description above, except that it pushes selecting the first item inside of the loop and in doing this, swaps the order of selection and updating inside of the loop. Lines 1-3 describes the initial placement of all vertices in the 'not yet seen' set. Line 4 ensures that the source, since it will have a key of zero while everyone else has a key of infinity, is the first vertex added to the tree. Line 5 places all vertex keys in a min-heap to allow for rapid removal of the min key. Line 6 controls the loop and will run |V| times (removing the source and then the other |V|-1 vertices). Line 7 pulls out the vertex with the minimum weight edge connecting it to the current tree. Lines 8-11 move all items that are in the unseen set and that are connected to the last node added into the fringe set (in the min-heap, the unseen set vertices have infinite keys, while the fringe vertices have keys with actual values) and updates the weights for edges into the tree as required for items in the fringe set. The second test on line 9 ensures that only the best routes into the tree are used. Line 10 preserves the edge information used to connect the chosen fringe vertex to the current tree.

[edit] 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.

[edit] 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 McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.