Data Structures and Algorithms with Object-Oriented Design Patterns in C++

## Prim's Algorithm

Prim's algorithm  finds a minimum-cost spanning tree of an edge-weighted, connected, undirected graph . 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 ). To construct the spanning tree, the algorithm constructs a sequence of spanning trees , each of which is a subgraph of G. The algorithm begins with a tree that contains one selected vertex, say . I.e., .

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

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

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

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

Figure: Operation of Prim's Algorithm