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

Login NowIn 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.

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.

Click here to submit your answer.

HAMROCSIT.COM

## Discussion