Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
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 3, 29, 39, and 41.

   program53001
Program: Prim's algorithm.

The PrimsAlgorithm method takes two arguments. The first is an 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 the number of the start vertex, tex2html_wrap_inline70863.

The PrimsAlgorithm method returns a minimum-cost spanning tree represented as an undirected graph. Therefore, the return value is a Graph.

The running time of Prim's algorithm is asymptotically the same as Dijkstra's algorithm. That is, the worst-case running time is

displaymath71291

when adjacency lists are used, and

displaymath71292

when adjacency matrices are used to represent the input graph.


next up previous contents index

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