Logo Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Prim's Algorithm

Prim's algorithm  finds a minimum-cost spanning tree of an edge-weighted, connected, undirected graph tex2html_wrap_inline70093. The algorithm constructs the minimum-cost spanning tree of a graph by selecting edges from the graph one-by-one and adding those edges to the spanning tree.

Prim's algorithm is essentially a minor variation of Dijkstra's algorithm (see Section gif). To construct the spanning tree, the algorithm constructs a sequence of spanning trees tex2html_wrap_inline71705, each of which is a subgraph of G. The algorithm begins with a tree that contains one selected vertex, say tex2html_wrap_inline70955. That is, tex2html_wrap_inline71711.

Given tex2html_wrap_inline71713, we obtain the next tree in the sequence as follows. Consider the set of edges given by

displaymath71699

The set tex2html_wrap_inline71715 contains all the edges tex2html_wrap_inline71717 such that exactly one of v or w is in tex2html_wrap_inline71477 (but not both). Select the edge tex2html_wrap_inline71725 with the smallest edge weight,

displaymath71700

Then tex2html_wrap_inline71727, where tex2html_wrap_inline71729 and tex2html_wrap_inline71731. After tex2html_wrap_inline71603 such steps we get tex2html_wrap_inline71735 which is the minimum-cost spanning tree of G.

Figure gif illustrates how Prim's algorithm determines the minimum-cost spanning tree of the graph tex2html_wrap_inline71691 shown in Figure gif. The circled vertices are the elements of tex2html_wrap_inline71477, the solid edges represent the elements of tex2html_wrap_inline71743 and the dashed edges represent the elements of tex2html_wrap_inline71715.

   figure52387
Figure: Operation of Prim's algorithm.