Q. Between 4 rooms of a house, there are certain connections between those rooms for electricity. A matrix is used for specifying the connection details between rooms and the details of connectivity is maintained in a matrix –

A 
B 
C 
D 
A 
0 
3 
0 
23 
B 
45 
0 
32 
3 
C 
5 
5 
0 
3 
D 
45 
3 
0 
0 
Where the integers represent the connection wire length between those two rooms.
Write an algorithm to eliminate the redundant use of wires such that only minimum wire required is in use and all rooms are connected.
Its not necessary that rooms are connected directly. If A connects to B and B connects to C, we can say A,B,C are connected.
A. I related it as a minimum spanning tree problem.
 Create a method which can tell you if all nodes are connected.
 Store all values in descending order. Also, store the respective indices.
 Start eliminating nodes with maximum values. Spare only if it breaks the connectivity. We can call function created in first step to check it.
Complexity of our algorithm –
 Method to check if tree is still connected. This operation takes O(n) time.
 Removing redundant connections (A to B, B to A). This operation takes O(n) time.
 Sorting of all the elements. This operation takes O(nlogn) time.
 Eliminating all nodes and checking the connectivity. O(n square) Since, at every node we have to call check connectivity.
Since, O(n square) dominates, its the overall complexity of this approach.
Implementing it in the code for this was very challenging.