Given an input graph find the second best minimum spanning tree. A second best minimum spanning tree is a tree whose total weight of the edges is greater than the minimum spanning tree and lesser than any other spanning tree of the graph. For example in given below input graph ( in image below ) minimum spanning tree is with total weight 6 and second best minimum spanning tree is with total weight 9. Note that the second best minimum spanning tree need not to be unique.

Second best minimum spanning tree

Second best minimum spanning tree

The second best minimum spanning tree is a complex problem. This problem is taken from “introduction to algorithm”. How to proceed with problem.

https://webdocs.cs.ualberta.ca/~xianchen/teaching/TutorialW0611.pdf



Related Contents to follow