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

This answer is restricted. Please login to view the answer of this question.

Login Now

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:

- Hamro CSIT

Here, no of vertices  = 4

So, all spanning tree should have 3 edges

- Hamro CSIT

Cost = 15

- Hamro CSIT

Cost = 6

- Hamro CSIT

Cost = 9- Hamro CSIT

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:

Kruskal Algorithm

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.

Kruskal Algorithm

Step 2 – Add the edge DE with weight 2 to the MST as it is not creating the cycle.

Kruskal Algorithm

Step 3 – Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Kruskal Algorithm

Step 4 – Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.

Kruskal Algorithm

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 –

Kruskal Algorithm

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

If you found any type of error on the answer then please mention on the comment or report an answer or submit your new answer.
Leave your Answer:

Click here to submit your answer.

Discussion
0 Comments
  Loading . . .