Prim's algorithm

From Free net encyclopedia

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 DJP algorithm or Jarnik algorithm.

It works as follows:

create a tree containing a single vertex, chosen arbitrarily from the graph
create a set containing all the edges in the graph
loop until every edge in the set connects two vertices in the tree
- remove from the set an edge with minimum weight that connects a vertex in the tree with a vertex not in the tree
- add that edge to the tree

Using a simple binary heap data structure, 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 Proof of correctness
3 References
4 External links

[edit]

Example

Image:Prim Algorithm 0.svg	This is our original tree. 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.
Image:Prim Algorithm 1.svg	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.
Image:Prim Algorithm 2.svg	The next vertex chosen is the vertex nearest to either D or A. B is 9 away (from D), E is 15, and F is 6. 6 is the smallest, so we highlight the vertex F and the arc DF.
Image:Prim Algorithm 3.svg	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.
Image:Prim Algorithm 4.svg	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.
Image:Prim Algorithm 5.svg	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.
Image:Prim Algorithm 6.svg	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]

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 for P which has the greatest number of edges in common with Y. If Y₁=Y then Y is a minimum spanning tree. Otherwise, let e be the first edge that was added when Y was constructed. Let V be the set of vertices of Y - e. Then one endpoint of e is in V and another 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 tree obtained by removing f and adding e from Y₁. It shows that Y₂ is a tree that is more common with Y than with Y₁. If Y₂ equals Y, QED. If not, we can find a tree, Y₃ with one more edge in common with Y than Y₂ and so forth. Continuing this way produces a tree that is more in common with Y than with the preceding tree. Since there are finite number of edges in Y, the sequence is finite, so there will eventually be a tree, Y_h, which 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 0262032937. Section 23.2: The algorithms of Kruskal and Prim, pp.567–574.