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