Follow Us :

DT Q12

12Consider the following graph:
Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?
  • Option : D
  • Explanation :
    Ordering the weights, the sequence obtained is
    1, 1, 2, 2, 3, 3, 4, 4, 5, 6, 7
    Now, in order to obtain minimum spanning tree using Kruskal's algorithm, we have to add edges with weights in increasing order such that weight of the spanning tree is minimum.
    In option (D), weights of the edges are 1, 1, 2, 3, 2 which contradicts Kruskal's algorithm.
Cancel reply

Your email address will not be published. Required fields are marked *


Cancel reply

Your email address will not be published. Required fields are marked *