GATE IT 2008 | Question: 45

Question

For the undirected, weighted graph given below, which of the following sequences of edges represents a correct execution of Prim's algorithm to construct a Minimum Span­ning Tree?

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

Comments

@Akash 15 in option c (d,a) is 5 and (a,b) is 1 then how c is correct?

---

@pavansan After visiting edge $(d,a)$ we are now at $a$. Edges associated with $a$ are with weights $1,6$ and we will take minimum which is $(a,b)$

 

---

@Akash 15 ohh it works like that aa i am calculating like kruskal sorry now understood

Answer 1

Prim's algorithm starts with from any vertex and  expands the MST by adding one vertex in each step which is close to the Intermediate MST(made till previous step).

Therefore, correct answer would be (C).

(A): $(d,f)$ is chosen but neither d  nor f vertices are part of the previous MST(MST made till previous step).

(B): $(g,h)$ is chosen but neither g or h vertices are part of the previous MST(MST made till previous step).

(D): $(f,c)$ is chosen but at that point $(f,d)$ is close to the intermediate MST.

Comments

If we are building a MST starting with a node say 'x', then the first edge to be added to the MST must be the edge with the least weight of all the edges incident on 'x'.

So, from this the following explanation follows.

A) (a,b),(a,d).........needs to be the order. Hence Option A eliminated.

B) (c,f).........needs to be the order, if we build MST starting with 'c'. Hence Option B is eliminated.

D) (h,g),(g,i),(h,f),(f,d).........needs to be the order. Hence Option D eliminated.

---

In option c ,there is a mistake , we have not visited g yet so we can not go from g to h

---

Can anyone explain why (d, g) was not choosen and why (g, h) was choosen?
I mean (d, g) is shorter than (d-f-h-g)

Answer 2

(C) is the answer.

First thing that we note is that Prims Algorithm, during execution, always GENERATES A SUBSET OF EDGES THAT IS CONNECTED. So prims algo always generates a connected component during its execution.

second thing to note is that, only getting a connected graph does not suffice here. The edge chosen next must be the smallest possible edge as per GREEDY strategy.

So lets check the options:

(A) (a,b) if fine .but second edge (d,f) is nowhere connected to previous edge. Therefore (A) is eliminated.

(B) I will sraight away go to the point. In choosing edge (g,h) we scan previous edges and DON'T find 'g' or 'h' in any of the order pairs. So (g,h) is not adjacent  to any of them. So (B) also eliminated. You can do this by marking the graph as well.

(D) In (D) option, at every stage you will find the graph connected BUT lets check for other property: GREEDINESS. When we choose (f,c) and (f,d) this order violate the greedy approach. Because (f,d) has cost 2 and should be included before (f,c). Therefore false.

(C) this satisfies all the required properties. TRUE

Comments

Dear Sandeep,

On page 677 of Discrete Mathematics by Kenneth Rosen, it is written that- In Prim's Algo,  first edge to be chosen is the minimum weight edge and then grow the tree as you have explained in your comment. 

Considering this, first edge must be (a,b) and then next (a,d) and so on.

But there is no such option. 

Actually, this question is wrong.

But if we go by arbitrary choosing the first node, then option is C.

Thank you so much for your prompt reply. 

---

Dhananjay,

May be that is mentioned BUT you dint understand the concept. THIS QUESTION IS ALSO CORRECT. I wll let you know how !!

first edge chosen is minimum BUT that is for a particular vertex that can be chosen arbitrarily. In option (C) you chose a vertex randomly that is d here. Now you have to choose,among the adjacent edges of 'd', edge that is minimum. You can see, (d,f) is the minimum weight edge among adjacent edges of 'd'.

Whenever we choose any arbitrary vertex, next edge that we choose we make sure that edge is minimum. And realize that to reach that vertex no other edge will be used because we have already chosen the edge. So we can start from any VERTEX and choose the edge that is minimum among all the adjacent edges for that.

I hope it clears .

---

if they say that use the kruskal inplace of prims then what is the answer. as per my knowledge thats also gives the same answer plz verify.

---

@rajan

if its kruskals then it should be OPTION A i suppose

---

This answer is the best one and tells me everything I need to know about testing edge sequences for validity without running Prim's algorithm directly. Running Prim's on various source vertices will take up a lot of time in the exam.

Note that the greedy property here is to be checked on each node, as opposed to on the entire sequence of edges (local greedy choice leads to global optimum). For e.g. in option D), $h-g$ appears before $g-i$ even though $h-g$ has more weight, but this is fine. What we should check is that $h-g$ appears before $h-f$, and it does. D) fails this local greediness property when $f-c$ appears before $f-d$.

Answer 3

Option A: We start with vertex A:

As per working of Prim's algorithm, after (a,b) the selected edge would be (a,d).

Hence option A is false.

Option B: Here, we start with vertex C:

Now here first edge chosen is (c,e) which is of higher cost than (c,f), which is not possible.

Hence, option B is false.

Option C: Here, we start with vertex D. 

The given sequence here is correct, you can check it manually.

Option D: Just like option B:

Here we start with vertex G, and select (g,h) before (g,i), where (g,h) is of higher cost and this is not possible.

Answer 4

1. df is wrong
2. first edge itself is wrong, if you’re starting at c, cf should be the first edge
3. correct, no voilations
4. after hf, fd should have been chosen

Answer 5

In this question they are asking the edge selction sequence , So that here we need to apply the prims algo according to given options bcoz in prims algo can be start from any vertex,

For ,

     option A → we start from vertex $a$

     option B→ we start from vertex $c$

     option C → we start from vertex $d$

     option D → we start from vertex $h$

 

After performing prims algo we get option $ C$ as a Correct option