Question

Consider the graph shown below. Which of the following are the edges in the MST of the given graph?

(a) (a-c)(c-d)(d-b)(d-b)

(b) (c-a)(a-d)(d-b)(d-e)

(c) (a-d)(d-c)(d-b)(d-e)

(d) (c-a)(a-d)(d-c)(d-b)(d-e)

The question was posed to me during a job interview.

This question is from Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

The correct option is (c) (a-d)(d-c)(d-b)(d-e)

Explanation: The minimum spanning tree of the given graph is shown below. It has cost 56.