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

Implementation

An implementation of Kruskal's algorithm is shown in Program gif. The KruskalsAlgorithm function takes as its lone argument a const reference to an edge-weighted, undirected graph. This implementation assumes that the edge weights are instances of the Int class defined in Program gif. The routine computes the minimum-cost spanning tree and returns it in the form of an edge-weighted undirected graph. The function allocates the storage, constructs the graph and returns a reference to a Graph instance.

   program54744
Program: Kruskal's Algorithm

The main data structures used by the routine are a priority queue to hold the edges, a partition to detect cycles and a graph for the result. This implementation uses a BinaryHeap (Section gif) for the priority queue, a PartitionAsForest (Section gif) for the partition and a GraphAsLists for the spanning tree.


next up previous contents index

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