Program 2

Overview

One of the applications of minimum-spanning trees is connections to a power source. This problem models a city growing its power grid from a power station out to various neighboring communities. The problem proceeds in two phases. In the first phase, a complete graph is presented. In the second phase, costs are changed. The connection must still complete, even though the result may no longer be a MST on the final graph.

Description

For this program, you will implement Prim's algorithm for finding a minimum spanning tree. The initial graph is a dense graph represented as an adjacency (cost) matrix. To make things easier, the first line is the number of nodes in the first part. The main diagonal is all 0. Please note that the costs in the graph do not necessarily obey a euclidean metric or even the triangle inequality. The graph is guaranteed to be symmetric. Your job is to find a minimum-spanning tree, starting at node 0. This starts connecting communities immediately to the grid with the least overall cost.

You will print out the MST at the halfway point (rounded down). Print the from node followed by the to node followed by a newline for each edge in the tree thus far. Then print an empty line.

After the inital half-MST is created, costs are adjusted via a list of edges in (from to cost) format. I will only provide the edge in one direction, but the cost is still symmetric. Note that if both nodes are already in the MST at this point, it will have no effect. However, if at least one of the nodes is not in the MST yet, update the cost to reflect the new value.

At this point, finish the MST and print it out.

Sample Input

          
10
0 143 158 96 144 176 6 128 113 195
143 0 40 28 13 131 36 129 139 54
158 40 0 38 181 164 115 34 60 136
96 28 38 0 74 4 108 104 127 141
144 13 181 74 0 97 167 125 39 52
176 131 164 4 97 0 159 192 105 151
6 36 115 108 167 159 0 85 19 124
128 129 34 104 125 192 85 0 75 68
113 139 60 127 39 105 19 75 0 14
195 54 136 141 52 151 124 68 14 0

2 8 142
1 5 152
5 6 72
6 9 99
3 4 156
2 6 95
1 2 119
0 6 5
2 4 55
1 4 137

Sample Output