10.2 Minimum Spanning Tree: Prim's AlgorithmA spanning tree of an undirected graph G is a subgraph of G that is a tree containing all the vertices of G. In a weighted graph, the weight of a subgraph is the sum of the weights of the edges in the subgraph. A minimum spanning tree (MST) for a weighted undirected graph is a spanning tree with minimum weight. Many problems require finding an MST of an undirected graph. For example, the minimum length of cable necessary to connect a set of computers in a network can be determined by finding the MST of the undirected graph containing all the possible connections. Figure 10.4 shows an MST of an undirected graph. Figure 10.4. An undirected graph and its minimum spanning tree.If G is not connected, it cannot have a spanning tree. Instead, it has a spanning forest. For simplicity in describing the MST algorithm, we assume that G is connected. If G is not connected, we can find its connected components (Section 10.6) and apply the MST algorithm on each of them. Alternatively, we can modify the MST algorithm to output a minimum spanning forest. Prim's algorithm for finding an MST is a greedy algorithm. The algorithm begins by selecting an arbitrary starting vertex. It then grows the minimum spanning tree by choosing a new vertex and edge that are guaranteed to be in a spanning tree of minimum cost. The algorithm continues until all the vertices have been selected. Let G = (V, E, w) be the weighted undirected graph for which the minimum spanning tree is to be found, and let A = (a_{i}, j) be its weighted adjacency matrix. Prim's algorithm is shown in Algorithm 10.1. The algorithm uses the set V_{T} to hold the vertices of the minimum spanning tree during its construction. It also uses an array d[1..n] in which, for each vertex v (V - V_{T} ), d [v] holds the weight of the edge with the least weight from any vertex in V_{T} to vertex v. Initially, V_{T} contains an arbitrary vertex r that becomes the root of the MST. Furthermore, d[r] = 0, and for all v such that v (V - V_{T} ), d[v] = w(r, v) if such an edge exists; otherwise d[v] = . During each iteration of the algorithm, a new vertex u is added to V_{T} such that d[u] = min{d [v]|v (V - V_{T} )}. After this vertex is added, all values of d[v] such that v (V - V_{T}) are updated because there may now be an edge with a smaller weight between vertex v and the newly added vertex u. The algorithm terminates when V_{T} = V. Figure 10.5 illustrates the algorithm. Upon termination of Prim's algorithm, the cost of the minimum spanning tree is . Algorithm 10.1 can be easily modified to store the edges that belong in the minimum spanning tree. Figure 10.5. Prim's minimum spanning tree algorithm. The MST is rooted at vertex b. For each iteration, vertices in V_{T} as well as the edges selected so far are shown in bold. The array d[v] shows the values of the vertices in V - V_{T} after they have been updated.In Algorithm 10.1, the body of the while loop (lines 10-13) is executed n-1 times. Both the computation of min{d[v]|v (V - V_{T} )} (line 10), and the for loop (lines 12 and 13) execute in O (n) steps. Thus, the overall complexity of Prim's algorithm is Q(n^{2}). Algorithm 10.1 Prim's sequential minimum spanning tree algorithm.1. procedure PRIM_MST(V, E, w, r) 2. begin 3. V_{T} := {r}; 4. d[r] := 0; 5. for all v (V - V_{T} ) do 6. if edge (r, v) exists set d[v] := w(r, v); 7. else set d[v] := ; 8. while V_{T} V do 9. begin 10. find a vertex u such that d[u] :=min{d[v]|v (V - V_{T} )}; 11. V_{T} := V_{T} {u}; 12. for all v (V - V_{T} ) do 13. d[v] := min{d[v], w(u, v)}; 14. endwhile 15. end PRIM_MST Parallel FormulationPrim's algorithm is iterative. Each iteration adds a new vertex to the minimum spanning tree. Since the value of d[v] for a vertex v may change every time a new vertex u is added in V_{T} , it is hard to select more than one vertex to include in the minimum spanning tree. For example, in the graph of Figure 10.5, after selecting vertex b, if both vertices d and c are selected, the MST will not be found. That is because, after selecting vertex d, the value of d[c] is updated from 5 to 2. Thus, it is not easy to perform different iterations of the while loop in parallel. However, each iteration can be performed in parallel as follows. Let p be the number of processes, and let n be the number of vertices in the graph. The set V is partitioned into p subsets using the 1-D block mapping (Section 3.4.1). Each subset has n/p consecutive vertices, and the work associated with each subset is assigned to a different process. Let V_{i} be the subset of vertices assigned to process P_{i} for i = 0, 1, ..., p - 1. Each process P_{i} stores the part of the array d that corresponds to V_{i} (that is, process P_{i} stores d [v] such that v V_{i}). Figure 10.6(a) illustrates the partitioning. Each process P_{i} computes d_{i}[u] = min{d_{i}[v]|v (V - V_{T}) V_{i}} during each iteration of the while loop. The global minimum is then obtained over all d_{i}[u] by using the all-to-one reduction operation (Section 4.1) and is stored in process P_{0}. Process P_{0} now holds the new vertex u, which will be inserted into V_{T}. Process P_{0} broadcasts u to all processes by using one-to-all broadcast (Section 4.1). The process P_{i} responsible for vertex u marks u as belonging to set V_{T}. Finally, each process updates the values of d[v] for its local vertices. Figure 10.6. The partitioning of the distance array d and the adjacency matrix A among p processes.When a new vertex u is inserted into V_{T}, the values of d[v] for v (V - V_{T}) must be updated. The process responsible for v must know the weight of the edge (u, v). Hence, each process P_{i} needs to store the columns of the weighted adjacency matrix corresponding to set V_{i} of vertices assigned to it. This corresponds to 1-D block mapping of the matrix (Section 3.4.1). The space to store the required part of the adjacency matrix at each process is Q(n^{2}/p). Figure 10.6(b) illustrates the partitioning of the weighted adjacency matrix. The computation performed by a process to minimize and update the values of d[v] during each iteration is Q(n/p). The communication performed in each iteration is due to the all-to-one reduction and the one-to-all broadcast. For a p-process message-passing parallel computer, a one-to-all broadcast of one word takes time (t_{s} + t_{w}) log p (Section 4.1). Finding the global minimum of one word at each process takes the same amount of time (Section 4.1). Thus, the total communication cost of each iteration is Q(log p). The parallel run time of this formulation is given by Since the sequential run time is W = Q(n^{2}), the speedup and efficiency are as follows: From Equation 10.1 we see that for a cost-optimal parallel formulation (p log p)/n = O (1). Thus, this formulation of Prim's algorithm can use only p = O (n/log n) processes. Furthermore, from Equation 10.1, the isoefficiency function due to communication is Q(p^{2} log^{2} p). Since n must grow at least as fast as p in this formulation, the isoefficiency function due to concurrency is Q(p^{2}). Thus, the overall isoefficiency of this formulation is Q(p^{2} log^{2} p). |