Question

Which of the following is true?

(a) Prim’s algorithm initialises with a vertex

(b) Prim’s algorithm initialises with a edge

(c) Prim’s algorithm initialises with a vertex which has smallest edge

(d) Prim’s algorithm initialises with a forest

This question was addressed to me in examination.

Origin of the question is Minimum Spanning Tree in division Minimum Spanning Tree of Data Structures & Algorithms II

Answer 1

Right answer is (a) Prim’s algorithm initialises with a vertex

The explanation is: Steps in Prim’s algorithm: (I) Select any vertex of given graph and add it to MST (II) Add the edge of minimum weight from a vertex not in MST to the vertex in MST; (III) It MST is complete the stop, otherwise go to step (II).