Mastering Algorithms with C

Implementation and Analysis of Minimum Spanning Trees

To compute a minimum spanning tree for an undirected, weighted graph, we first need a way to represent weighted graphs using the basic abstract datatype for graphs presented in Chapter 11. We also need a way to keep track of the information that Prim’s algorithm requires for vertices and edges. This is the point of the MstVertex structure; it is used for vertices in graphs for which we plan to compute minimum spanning trees (see Example 16.2). The structure consists of five members: data is the data associated with the vertex, weight is the weight of the edge incident to the vertex, color is the color of the vertex, key is the key value of the vertex, and parent is the parent of the vertex in the minimum spanning tree.

Building a graph of MstVertex structures is nearly the same as building a graph containing other types of data. To insert a vertex into the graph, we call graph_ins_vertex and pass an MstVertex structure for data. Similarly, to insert an edge, we call graph_ins_edge and pass MstVertex structures for data1 and data2. When we insert a vertex, we set only the data member of the MstVertex structure. When we insert an edge, we set the data member of data1, and the data and weight members of data2. In data2, the weight member is the weight of the edge from the vertex represented by data1 to the vertex represented by data2. In practice, weights are usually computed and stored as floating-point numbers. Since key values ...