Calculating Spanning tree Cost & Minimum Spanning Tree.
Cost of a spanning tree:
- The cost of the spanning tree is the sum of the weights of all the edges in the tree.
- Example :
- One of the spanning tree of above graph would be
- What would be the cost of this spanning tree? 17 + 7 + 0 which is 24
- One of the spanning tree of above graph would be
Minimum Spanning tree
- A minimum spanning tree, abbreviated as MST, is the spanning three having the minimum some cost, say S1, S2, S3, S4 and S5 having cost 100, 104, 500, 400 and 10 respectively, but the one incurring the minimum cost is called the minimum spanning tree. Here, S5 having cost 10 would be the minimum spanning tree.