Minimum Spanning Tree Problem

Question

Comments

Kruskal's algorithm, adds edges with minimum weights and as such may be at intermediate stages sometimes the edges added are not connected so, it gives rise to a forest but in case of Prim's, all the edges are added with respect to edges already added so forest can never be formed, I think (b) is the answer.

---

is it A ? kruskal always produces intermediate forest

---

option b is correct...kruskal algorithm may give forest.

Answer 1

Forest : Collection of Trees

In Kruskal Algorithm we place all the edges of the graph in non-decreasing order and start selecting the edges from the smallest edge and for rest of the graph we do the same recursively until and unless that edge we are picking results in a circuit. If that happens we skip that edge and continue the algorithm for rest of the graph. This Algorithm may lead to intermediate forests in graph.

In Prim's algorithm we start with a particular vertex in graph and select smallest edge from that vertex we do this again for that sub-graph and recursively do this for all edges but in this algorithm there is no possibility of forest because we keep on adding edges on the same sub-graph.

So the answer is B

Comments

yes and prim can produce tree but not forest

---

prims always produce tree.

Answer 2

option b

in this example first graph using kruskal intermidiate result is not a forest .

but in second graph intermediate result is forest.