Data Structures and Algorithms
with Object-Oriented Design Patterns in C++ 
An implementation of Prim's algorithm is shown in Program 
.
This implementation is almost identical
to the version of Dijkstra's algorithm given in Program .
In fact, there are only four differences between the two algorithms.
These are found on lines 1, 23, 38, and 40-41.
The PrimsAlgorithm function takes two arguments.
The first is a const reference to a undirected graph instance.
We assume that the graph is edge-weighted
and that the weights are instances of the
Int class defined in Program .
The second argument is a const reference to the start node.
The PrimsAlgorithm routine returns a minimum-cost spanning tree represented as an undirected graph. Therefore, the return value is a reference to a Graph instance. The function allocates the storage, constructs the spanning tree and returns a reference to that graph.
The running time of Prim's algorithm is asymptotically the same as Dijkstra's algorithm. I.e., the worst-case running time is
when adjacency lists are used, and
when adjacency matrices are used to represent the input graph.
Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.
