UGC NET CSE | October 2020 | Part 2 | Question: 78

Question

Consider the undirected graph below:

Using Prim’s algorithm to construct a minimum spanning tree starting with node $a$, which one of the following sequences of edges represents a possible order in which the edges would be added to construct the minimum spanning tree?

• A. $(a,b), (a,h), (g,h), (f,g), (c,f), (c,i), (c,d), (d,e)$
• B. $(a,b), (b,h), (g,h), (g,i), (c,i), (c,f), (c,d), (d,e)$
• C. $(a,b), (b,c), (c,i), (c,f), (f,g), (g,h), (c,d), (d,e)$
• D. $(a,b), (g,h), (g,f), (c,f), (c,i), (f,e), (b,c), (d,e)$ 

Answer 1

Prim’s algorithm may informally be described as performing the following steps:

1. Initialize a tree with a single vertex, chosen arbitrarily from the graph.

2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.

3. Repeat step 2 (until all vertices are in the tree)                                                                                         Here we have to start with vertex a so first edge must be (a,b)                                                                  next either ( b.c) or (a,h) {hence option  B,D are out  if  we go with (b,c) then next must be (c,i) followed by (c,f)  (f,g) then (g,h)  and   (c,d) and (d,e)                                                                                               which is option C) hence it is correct ans

  if we go with (a,h) next must be (h,g) or  (g,h) as in option A hence  is  also correct  (although order is changed)  

Both A, C are correct as per offiical key

Answer 2

ANSWER IS OPTIONN C

PRIMS ->GROWS LIKE TREE

BY TAKING 3EDGES U WILL  SEE   OPTIONN C MATCHES