The GATE Grind

GATE 2009 CS – Question 38

Algorithms · Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths · 2 marks · Multiple choice

For the graph shown, which is NOT a possible sequence of edges added by Kruskal’s minimum-spanning-tree algorithm?

Diagram for GATE 2009 CS question 38
  1. (b, e), (e, f), (a, c), (b, c), (f, g), (c, d)
  2. (b, e), (e, f), (a, c), (f, g), (b, c), (c, d)
  3. (b, e), (a, c), (e, f), (b, c), (f, g), (c, d)
  4. (b, e), (e, f), (b, c), (a, c), (f, g), (c, d)

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (D) (b, e), (e, f), (b, c), (a, c), (f, g), (c, d)

Explanation

We are sorry we couldn't write detailed soluition for this, we are working on it!, please consider asking your own AI, its just 2-3 clicks with very minimum effort

More Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions

All Graph Algorithms: Traversals, Minimum Spanning Trees, Shortest Paths questions →