Question

Which of the following is false about the Kruskal’s algorithm?

(a) It is a greedy algorithm

(b) It constructs MST by selecting edges in increasing order of their weights

(c) It can accept cycles in the MST

(d) It uses union-find data structure

The question was posed to me in unit test.

Question is from Minimum Spanning Tree topic in division Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Right answer is (c) It can accept cycles in the MST

For explanation: Kruskal’s algorithm is a greedy algorithm to construct the MST of the given graph. It constructs the MST by selecting edges in increasing order of their weights and rejects an edge if it may form the cycle. So, using Kruskal’s algorithm is never formed.