Minimum spanning tree (MST)
https://www.computersprofessor.com/2016/12/minimum-spanning-tree-mst-minimum.html
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(n2) 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
