Minimum Cost Spanning Tree

What is a Spanning Tree?

Assume there is an undirected and connected graph G(V, E) with a spanning tree. G is a subgraph of G that is a tree that spans G (that is, it includes every vertex of G) (every edge in the tree belongs to G )

Here,

G = (V, E)

V = {1, 2, 3, 4, 5, 6}

E = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1)}

• A spanning tree is a subgraph of a graph
• We should take all the vertices from the graph
• There will be no cycle or cyclic graph in the Spanning tree.

no of adjacent in the graph G is |V|= 6, in the spanning tree we will have total |V| - 1 = 6 - 1 = 5 adjacent. So, we have to know how many spanning trees can be generated from a graph.

Let this graph G has four vertices.

V = {1, 2, 3, 4}

E = {(1, 2), (1, 4), (2, 4), (4, 3), (3, 2)}

Let's find out the possible spanning trees for G.

Cost= 14

Cost= 13

Cost= 9

Can we have a minimum cost-spanning tree?

YES! We have the greedy method to solve the optimization problems.

We have two Algorithms for finding out the minimum cost-spanning tree.

1. Prim's Algorithm
2. Kruskal Algorithm

Prim's Algorithm

Total Cost = 10 + 25 + 22 + 12 + 15 + 14= 99

Kruskal Algorithm

Total Cost = 10 + 25 + 22 + 12 + 15 + 14= 99

Do it yourself