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

Implementation

An implementation of Prim's algorithm is shown in Program gif. This implementation is almost identical to the version of Dijkstra's algorithm given in Program gif. In fact, there are only four differences between the two algorithms. These are found on lines 1, 23, 38, and 40-41.

   program53687
Program: Prim's Algorithm

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 gif. 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

displaymath72639

when adjacency lists are used, and

displaymath72640

when adjacency matrices are used to represent the input graph.


next up previous contents index

Bruno Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.