Question 1.
We have discussed Prim's algorithm in class for computing the minimum spanning tree (MST). The first step is to codify the network information, i.e., how do we represent the link casts? One way is to use a matrix representation. If the link casts have been expressed as a matrix C, then the (i, j)th element of the matrix gives the cost of the link between i and j (obviously, if i = j, Cii = 0, for all i). For example, the cost matrix for the network shown in Fig. 1 is (first row/column is for node A, second row/column is for node B, etc.):
C =
| 0 |
1 |
5 |
2 |
∞ |
∞ |
| 1 |
0 |
2 |
6 |
∞ |
∞ |
| 5 |
2 |
0 |
1 |
3 |
∞ |
| 2 |
6 |
1 |
0 |
∞ |
4 |
| ∞ |
∞ |
3 |
∞ |
0 |
1 |
| ∞ |
∞ |
∞ |
4 |
1 |
0 |
You can assume that the user would not make any error in entering the link cost matrix (i.e., the matrix would be symmetric, non-negative, and all elements along the leading diagonal will be 0). That is, your code does not need to check for potential errors in the link cost matrix.
Write a function `computePrimMST(sourceID,C)' which takes as inputs the source node ID and the link cost matrix and returns the MST. The pseudocode is available on slide-101 of Chapter-5 notes. The function should return the MST as a 3-column list. The first two columns define the edge chosen and the third column lists the cost of that edge. For example, for the network in Fig. 1, the MST returned by the function could be:
| 1 |
2 |
1 |
| 2 |
3 |
2 |
| 3 |
4 |
1 |
| 3 |
5 |
3 |
| 5 |
6 |
1 |
This means that the edges chosen are (from top to bottom): (i) (A, B) with a cost of 1, (ii) (B, C) with a cost of 2, (iii) (C, D) with a cost of 1, (iv) (C, E) with a cost of 1, and (v) (E, F) with a cost of 1. The total cost of the MST is therefore 8.
You cannot use built in functions which directly compute the MST or im¬plement Prim's algorithm.
Figure 1: Network for Problem 1.