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.