10.2 Minimum Spanning Tree: Prim's Algorithm

A 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.

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.

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²).

Algorithm 10.1 Prim's sequential minimum spanning tree algorithm.

1.   procedure PRIM_MST(V, E, w, r) 
2.   begin 
3.      VT := {r}; 
4.      d[r] := 0; 
5.      for all v  (V - VT ) do 
6.         if edge (r, v) exists set d[v] := w(r, v); 
7.         else set d[v] := ; 
8.      while VT  V do 
9.      begin 
10.        find a vertex u such that d[u] :=min{d[v]|v  (V - VT )}; 
11.        VT := VT  {u}; 
12.        for all v  (V - VT ) do 
13.            d[v] := min{d[v], w(u, v)}; 
14.     endwhile 
15.  end PRIM_MST 

Parallel Formulation

Prim'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₀. Process P₀ now holds the new vertex u, which will be inserted into V_T. Process P₀ 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.

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²/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²), the speedup and efficiency are as follows:

Equation 10.1

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² log² p). Since n must grow at least as fast as p in this formulation, the isoefficiency function due to concurrency is Q(p²). Thus, the overall isoefficiency of this formulation is Q(p² log² p).