Spanning tree and Kruskal algorithm to find minimum spanning tree.
Spanning tree is a sub-graph that contains all the vertices and is a tree. A graph may have many spanning trees.
A minimum spanning tree or minimum weight spanning tree is then a spanning tree with weight less than or equal to the weight of every other spanning tree.
To find the minimum spanning tree two algorithm
- Kruskal algorithm.
- Prim algorithm.
Some example where minimum spanning tree is applies
- Design of a network group of individual who are separated by varying distance connected together in a telephone network minimum spanning tree can be used to determine the least costly paths with no cycles in this network thereby connecting everyone at a minimum cost.
- Minimum spanning tree would be finding airline routes.MST can be applied to optimize airline routes by finding the least costly paths with no cycles.
Kruskal Algorithm
Kruskal Algorithm is greedy algorithm that run in polynomial time. Kruskal algorithm that find a minimum spanning tree for a connected weighted graph.It finds a subset of the edges that forms a tree that includes every vertex where the total weight of all the edges in the tree is minimized.
Algorithm
Step 1: Sort the graph edges with respect to their weights.
Step 2: Start adding edges to the MST from the edge with the smallest weight until the edge of the largest weight.
Step 3: Only add edges which doesn't form a cycle edges which connect only disconnect components.
Example
Find minimum spanning tree using kruskal Algorithm.
Solution
Graph edges are
AB BC CD DA
2 1 3 4
Sort the edges with respect to their weights.
BC AB CD DA
1 2 3 4
So first take edge BC
Then take minimum weight edge AB
Then take minimum weight edge CD
Discard edge DA because that create cycle in a minimum spanning tree and loops or cycle not allowed in minimum spanning tree.
So cost of minimum spanning tree =6
0 Comments