in Others retagged by
1,913 views
1 vote
1 vote

The weight of minimum spanning tree in graph $G$, calculated using Kruskal’s algorithm is:

  1. $14$
  2. $15$
  3. $17$
  4. $18$
in Others retagged by
1.9k views

1 Answer

0 votes
0 votes

To find MST of a given graph using Kruskal’s algorithm we can follow $2$ steps process:

  1. Sort all the edges in increasing order of their weights.
  2. select the smallest edges and check if it forms a cycle with the spanning tree formed so far. if the cycle is not formed then include this edge, else discard it.

Step 1) Sort the edges of the given graph in increasing order of weight. so correct order is :$(2,3,4,5,6,7,8)$

Step 2) Draw the MST by selecting sorted edges one by one.

 We know that for $n$ vertices, the number of edges should be $(n-1)$ in MST. so for a given graph having $5$ vertices should have $4$ edges in MST.

  • we can select an edge having a weight $2$
  • we can also select an edge having a weight $3$
  • we can select edge having wight $4$
  • we can’t select an edge having a weight  $5$ because it forms a cycle.
  • next, we can select an edge having a weight $6$

our MST is done here. we can not take the edge with the weight of $7,8$ because it forms a cycle.

MST is as follow:

So Total cost of the minimum spanning tree is $(2+3+4+6)=15$

Option $(B)$ is correct.

Note: Similar type of question asked in Gate 2021

1 comment

in Kruskal's minimum spanning tree

1st sort all the edges in increasing or decreasing order of their weight

2nd pick the smallest element and check cycle is formed or not if a cycle is not formed ten pick that one

and repeat until there (v-1) edges in the spanning tree

in this tree, we arrange the weight is:2,3,4,6

and we pick as 2+3+4+6=15

answer is 15
0
0

Related questions