[Math] the length of the Minimum Spanning Tree

graph theorytrees

What is the length of the Minimum Spanning Tree for the following weighted graph?

Solution. The length of any minimum spanning tree for this graph (and there is more
than one) is 60.

The graph and the solution can be seen here
http://oi47.tinypic.com/1zb56w.jpg
enter image description here

Can someone explain how to do this problem, I'm having trouble understanding the process of finding the MST

Best Answer

Hint: The algorithm goes this way: Choose the edges weight from the lowest to highest. That edge will be added if it doesnt form a cycle with already choosen edges. The algorithm stops when a spanning tree is formed.

Related Question