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 ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access