## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required