Follow Us :

Nov2017 cs Q5

0. Consider the graph given below :


 Use Kruskal’s algorithm to find a minimal spanning tree for the graph. The List of the edges of the tree in the order in which they are choosen is?
 (1) AD, AE, AG, GC, GB, BF
 (2) GC, GB, BF, GA, AD, AE
 (3) GC, AD, GB, GA, BF, AE
 (4) AD, AG, GC, AE, GB, BF

  • Option : D
  • Explanation :
    Using Kruskal's algorithm for minimal spanning tree: First select the minimum weight edge ie 2 we have two options GC and AD Now select Next edge of minimum weight: for GC we have to select GB or AD and so on select minimum weight keep in mind no vertex left to visit. Here all option are matching with minimum spanning tree. So, option (D) is correct.
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 *