Question

Which of the following is true?

(a) Prim’s algorithm can also be used for disconnected graphs

(b) Kruskal’s algorithm can also run on the disconnected graphs

(c) Prim’s algorithm is simpler than Kruskal’s algorithm

(d) In Kruskal’s sort edges are added to MST in decreasing order of their weights

I got this question in exam.

I want to ask this question from Minimum Spanning Tree in section Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Correct option is (b) Kruskal’s algorithm can also run on the disconnected graphs

Easiest explanation - Prim’s algorithm iterates from one node to another, so it can not be applied for disconnected graph. Kruskal’s algorithm can be applied to the disconnected graphs to construct the minimum cost forest. Kruskal’s algorithm is comparatively easier and simpler than prim’s algorithm.