Given the graph below one of the following edges cannot be added in that order to find a minimum spanning tree algorithm.

Q

I. a-b

II. d-f

III. b-f

IV. d-c

V. d-e

1. AI, II , III, IV,V
2. BI, II, IV, III, V
3. CII, I, III, V, IV
4. DII, I, IV, III, V Q

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. II, I, III, V, IV

Explanation

The MST uses a–b (1), d–f (1), b–f (2), d–c (2) and d–e (3). Kruskal adds edges in non-decreasing weight order, so d–e (3) cannot come before d–c (2). Sequence C (II, I, III, V, IV) does exactly that; the other orders are valid.