1 votes 1 votes Algorithms minimum-spanning-tree graph-algorithms test-series + – pankaj_vir asked Mar 19, 2018 • edited Jul 16, 2022 by makhdoom ghaya pankaj_vir 2.1k views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Sukannya commented Mar 19, 2018 reply Follow Share 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. 1 votes 1 votes akshat sharma commented Mar 19, 2018 reply Follow Share is it A ? kruskal always produces intermediate forest 0 votes 0 votes Akshay Koli 4 commented Mar 19, 2018 reply Follow Share option b is correct...kruskal algorithm may give forest. 0 votes 0 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes 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 Mk Utkarsh answered Mar 20, 2018 • selected Mar 20, 2018 by pankaj_vir Mk Utkarsh comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented Mar 20, 2018 reply Follow Share yes and prim can produce tree but not forest 0 votes 0 votes Jason commented Mar 20, 2018 reply Follow Share prims always produce tree. 2 votes 2 votes Please log in or register to add a comment.
2 votes 2 votes option b in this example first graph using kruskal intermidiate result is not a forest . but in second graph intermediate result is forest. abhishekmehta4u answered Mar 20, 2018 abhishekmehta4u comment Share Follow See all 0 reply Please log in or register to add a comment.