• Choose a category
• All
• Classic-Fiction

By Root 1458 0

key value. Initially, this will be the start vertex since its key value is 0. After we select the vertex, we color it black. Next, for each white vertex v adjacent to u, if the weight of the edge (u, v) is less than the key value of v, we set the key value of v to the weight of (u, v) and we set the parent of v to u. We then repeat this process until all vertices have been colored black. As the minimum spanning tree grows, it consists of all edges in the graph that have a black vertex on either end.

Figure 16.1 illustrates the computation of a minimum spanning tree using Prim's algorithm. In the figure, the key value and parent of each vertex are displayed beside the vertex. The key value is to the left of the slash, and the parent is to the right. The edges shaded in light gray are the edges in the minimum spanning tree as it grows. The minimum spanning tree computed in the figure has a total weight of 17.

Figure 16.1. Computing a minimum spanning tree using Prim's algorithm

Interface for Minimum Spanning Trees

Name

mst

Synopsis

int mst(Graph *graph, const MstVertex *start, List *span, int (*match)

(const void *key1, const void *key2));

Return Value

0if computing the minimum spanning tree is successful, or -1 otherwise.

Description

Computes a minimum spanning tree for an undirected, weighted graph specified by graph. The minimum spanning tree is computed starting from the vertex specified by start. The operation modifies graph, so a copy should be made before calling the operation, if necessary. Each vertex in graph must contain data of type MstVertex. Assign a weight to each edge by setting the weight member of the MstVertex structure passed as data2 to graph_ins_edge. Use the data member of each MstVertex structure to store data associated with the vertex, such as an identifier. The match function for graph, which is set by the caller when initializing the graph with graph_init, should compare only the data members of MstVertex structures. This is the same function that should be passed as the match argument to mst. Once computed, information about the minimum spanning tree is returned in span, which is a list of MstVertex structures. In span, the vertex whose parent is set to NULL is the vertex at the root of the minimum spanning tree. The parent member of every other vertex points to the vertex that precedes it in the span. The vertices in span point to actual vertices in graph, so the caller must ensure that the storage in graph remains valid as long as span is being accessed. Use list_destroy to destroy span once it is no longer needed.

Complexity

O (EV 2), where V is the number of vertices in the graph and E is the number of edges. However, with a little improvement to the implementation presented here, Prim's algorithm runs in O (E lg V ) time (see the related topics at the end of the chapter).

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,