Made Easy Test Series 2024

Question

• A.

   

• A.

   

100. 

      

500. 

      

pls give all possible sequences possible for prims algo 

Answer 1

 

From the options its quite evident that we should start from A as our starting vertex.

One of the possible sequences of the prims algorithm is shown here :

	a	b	c	d	e	f	g	h	i
	∞   N	∞   N	∞   N	∞   N	∞   N	∞   N	∞   N	∞   N	∞   N
a		4  a	∞   N	∞   N	∞   N	∞   N	∞   N	8  a	∞   N
b			8  b	∞   N	∞   N	∞   N	∞   N	8  a	∞   N
c				7   c	∞   N	4  c	∞   N	8  a	2  c
i				7  c	∞   N	4  c	6  i	7  i
f				7  c	10  f		2  f	7  h
g				7  c	10  f			1  g
h				7  c	10  f
d					9  d
e

As per the order of relaxation we got a choice only between the edges ${a,h}$ and $ {b,c} $ , apart from these we have no choices ever in the entire algorithm.So option a and c are true .
Option d takes non adjacent edges which is true for $Kruskal’s$ algo not for $Prim’s$ and in option b the edge b,h is selected over {a,h} or {b,c} which has higher weight than the latter two.

Correct sequences are $a$ and $c$ 

Comments

@Psy Duck can you please tell me that how can i solve prims algo bcoz it takes a lot time to solve pls help me

---

@Ray Tomlinson The best way is to identify the starting vertex asked in the question.Then after identifying the starting vertex choose the smallest edge connecting the neighbours the starting vertex .If u see the algo this step is the relaxation of the edges to the adjacent vertices of the starting vertex.Now in each subsequent step add a new vertex by joining it with the already formed tree but with minimal cost .
U can refer this link : https://en.wikipedia.org/wiki/Prim%27s_algorithm