retagged by
13,858 views
25 votes
25 votes

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?

  1. $\text{(E, G), (C, F), (F, G), (A, D), (A, B), (A, C)}$
  2. $\text{(A, D), (A, B), (A, C), (C, F), (G, E), (F, G)}$
  3. $\text{(A, B), (A, D), (D, F), (F, G), (G, E), (F, C)}$
  4. $\text{(A, D), (A, B), (D, F), (F, C), (F, G), (G, E)}$
retagged by

4 Answers

Best answer
34 votes
34 votes

Answer is D.

$A$ and $B$ produce disconnected components with the GIVEN order in options which is NEVER allowed by prims's algorithm.

$C$ produces connected component every instant a new edge is added BUT when first vertex is chosen(first vertex is chosen randomly) first edge must be the minimum weight edge that is chosen . Therefore, $(A,D)$ MUST be chosen BEFORE $(A,B)$. Therefore,  $C$ is FALSE.

edited by
9 votes
9 votes
There are two correct sequences

i) (A, D), (A, B), (A, C), (C, F), (F, G), (G, E)  (not given in the options)

ii) (A, D), (A, B), (D, F), (F, C), (F, G), (G, E)  Option- D
0 votes
0 votes

 

Here 2 different Answers are possible .

 

in the first image we visited vertex $C$ firstly before vertex $F$ then we get the answer which does not match with anyone of them and this is wrong answer bcoz it makes cycle

iin the second image we visited vertex $F $  firstly before vertex  $C$ then we get the answer which does  match with option D 

 

so the final answer is option D

edited by
Answer:

Related questions

0 votes
0 votes
1 answer
2
Alakhator asked Oct 11, 2018
1,129 views
What is the time complexity of Prim algorithm without using min heap?