Find out the minimum spanning tree using Prim`s or Kruskal`s Algorithm. Remove one edge from MST. One vertex will become isolated. Add an edge, which is not in the MST, such that the vertex gets connected. Find out the increase in the total weight of the spanning tree.
Repeat this process with every edge of the MST.
Remove that edge, whose removal and addition of some other edge, will increase the total weight of MST by minimum. This will give the second minimum spanning tree.
For example:-
Let G be as follows:-
Remove AB from MST
Now to get a spanning tree, either DB is to be added or CD is to be added. Addition of DB will increase the weight by 2 units (i.e. 3 – 1) and addition of CD will increase the weight by 4 units (5-1). Therefore removal of AB will increase the weight of the next spanning tree by 2.
Now remove edge CB then CD or BC is to be added, edge CVD will increase the weight of the tree by 3 units (5-2) Similarly if AD is to be removed, it will be replaced by CD which will increase the weight of the tree by 3. Thus the second minimum spanning tree is obtained by remaining AB and adding DB.
