Minimum spanning tree (MST)

Minimum spanning tree (MST)

Minimum spanning tree for a weighted graph  G is a spanning tree such that the sum of the weight is less than (or)equal to sum of weights of every other spanning tree of G i.e., in a minimum spanning tree , the sum or weight ‘B’ of the edges is as small as possible . There are two important algorithms to obtain minimum spanning tree.They are :

Prisms algorithm

Kruskals algorithm

Prisms Algorithm :

we will consider all the vertices first when we select an edge with minimum weight . The algorithm proceeds by selecting adjacent edges with minimum weight care  should be taken for  not forming circuit.

Let us consider the prism’s algorithm with the help of some Ex :

Step 1:

Total weight =0

Step 2:

Total weight =10

Step 3:

Total weight =33

Step 4:

Total weight = 53

Step 5:

Total weight = 64

Step 6:

Total weight = 78

Step 7:

Total weight = 90

Time Complexity : This  algorithm spends more time in finding the smallest edge , so time of the algorithm basically depends on how do we search the edges.

 therefore prisms algorithm run in o(n²) times.

  

Kruskal’s Algorithm :

Always the minimum cast edge has to be selected.

Step 1:

Total weight =0

Step 2:

Total weight =10

Step 3:

Total weight =21

Step 4:

Total weight = 33

Step 5:

Total weight= 47

Step 6:

Total weight -67

Step 7:

Total weight=90