Mastering Algorithms With C - Kyle Loudon [200]
The mst operation begins by initializing every vertex in the list of adjacency-list structures. We set the initial key value of each vertex to DBL_MAX, except the start vertex, whose key value is set to 0.0. Recall that in the graph abstract datatype, a graph was represented as a list of adjacency-list structures, each of which contained one vertex and a set of vertices adjacent to it (see Chapter 11). We use the vertex stored in each adjacency-list structure to maintain the color, key value, and parent of the vertex. The point of maintaining this information in the list of adjacency-list structures, as opposed to vertices in the adjacency lists themselves, is that we can keep it in one place. Whereas a single vertex may appear in numerous adjacency lists, each vertex appears in the list of adjacency-list structures exactly once.
At the center of Prim's algorithm is a single loop that iterates once for each vertex in the graph. We begin each iteration by selecting the vertex that has the smallest key value among the white vertices. We color this vertex black where it resides in the list of adjacency-list structures. Next, we traverse the vertices adjacent to the selected vertex. As we traverse each vertex, we look up its color and key value in the list of adjacency-list structures. Once we have located this information, we compare it with the color and key value of the selected vertex. If the adjacent vertex is white and its key value is less than that of the selected vertex, we set the key value of the adjacent vertex to the weight of the edge between the selected vertex and the adjacent vertex; we also set the parent of the adjacent vertex to the selected vertex. We update this information for the adjacent vertex where it resides in the list of adjacency-list structures. We then repeat this process until all vertices have been colored black.
Once the main loop in Prim's algorithm terminates, we are finished computing the minimum spanning tree. At this point, we insert each black MstVertex structure from the list of adjacency-list structures into the linked list span. 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 weight member of each MstVertex structure is not populated because it is needed only for storing weights in adjacency lists. Figure 16.2 shows the list of MstVertex structures returned for the minimum spanning tree computed in Figure 16.1.
Figure 16.2. The list returned by mst for the minimum spanning tree computed in Figure 16.1
The runtime complexity of mst is O (EV 2), where V is the number of vertices in the graph and E is the number of edges. This comes from the main loop, in which we select vertices and compare weights and key values. For each of the V vertices we select, we first traverse V elements in the list of adjacency-list structures to determine which white vertex has the smallest key value. This part of the main loop is O (V 2) overall. Next, for each vertex adjacent to the vertex we select, we consult the list of adjacency-list structures for information about whether to change its key value and parent. Over all V vertices, the list is consulted E times, once for each of the E edges in all of the adjacency lists together. Each of these consultations requires O (V ) time to search the list. Therefore, for all V vertices that we select, an O (V ) operation is performed E times. Consequently, this part of the loop is O (EV 2), and the main loop overall is O (V 2 + EV 2), or O (EV 2). Since the loops before and after the main loop are O (V ), the runtime complexity of mst is O