retagged by
13,169 views
30 votes
30 votes

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?

  1. $\text{(a, b), (d, f), (f, c), (g, i), (d, a), (g, h), (c, e), (f, h)}$
  2. $\text{(c, e), (c, f), (f, d), (d, a), (a, b), (g, h), (h, f), (g, i)}$
  3. $\text{(d, f), (f, c), (d, a), (a, b), (c, e), (f, h), (g, h), (g, i)}$
  4. $\text{(h, g), (g, i), (h, f), (f, c), (f, d), (d, a), (a, b), (c, e)}$
retagged by

5 Answers

Best answer
32 votes
32 votes

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.

edited by
16 votes
16 votes
(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
0 votes
0 votes

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.

0 votes
0 votes
  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:

Related questions

0 votes
0 votes
3 answers
3
5 votes
5 votes
1 answer
4