What is minimum spanning tree? Explain Kruskal’s algorithm for finding minimum spanning tree.

Question

What is minimum spanning tree? Explain Kruskal&#8217;s algorithm for finding minimum spanning tree.

Suresh Chand · Accepted Answer

In a weighted graph, a minimum spanning tree is a subgraph of unidirected graph that includes all nodes and has minimum weight than all other nodes and has minimum weight than all other spaning trees of the same graph. The minimum spanning tree should contain all the vertices as in graph, and no of edges should be n-1 where n = no of vertices of graph. It should be connected ad no circuit should form. Example: The minimum spanning tree of following: Here, no of vertices  = 4 So, all spanning tree should have 3 edges Cost = 15 Cost = 6 Cost = 9 Cost = 10 Among these spanning trees, The tree with minimum cost is the minimum spanning tree. Kruskal Algorithm: Is is a algorithm which find a minimum spanning tree of a undirected edge-weighted graph. If a graph is connected, it finds minimum spanning tree. It basically takes a connected weighted graph finds the subset of edges of that graph and forms a tree that includes every vertex which includes minimum sum of weights among all the spanning trees that can be formed from the graph. Example: The minimum spanning tree of following using Kruskal Algrithm: The weight of the edges of the above graph is given in the below table - Edge AB AC AD AE BC CD DE Weight 1 7 10 5 3 4 2 Now, sort the edges given above in the ascending order of their weights. Edge AB DE BC CD AE AC AD Weight 1 2 3 4 5 7 10 Now, let's start constructing the minimum spanning tree. Step 1 - First, add the edge AB with weight 1 to the MST. Step 2 - Add the edge DE with weight 2 to the MST as it is not creating the cycle. Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop. Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle. Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the cycle, so discard it. Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so discard it. Step 7 - Pick the edge AD with weight 10. Including this edge will also create the cycle, so discard it. So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal's algorithm is - The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

What is minimum spanning tree? Explain Kruskal’s algorithm for finding minimum spanning tree.

Leave your Answer:

Hits Counter

Question

What is minimum spanning tree? Explain Kruskal’s algorithm for finding minimum spanning tree.

Leave your Answer: