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