The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
0 votes
186 views
Someone claims that Kruskal's algorithm for finding minimum spanning tree can return different spanning trees for the same input graph $G$. Do you agree with the claim? If so, why? If not, argue briefly why the claim is incorrect.
in Algorithms by Veteran (103k points) | 186 views

2 Answers

+7 votes

Yes I think the claim is true as

If Edge weights are not distinct then we can have multiple Spanning trees 

Suppose Consider an example

here we choose edges with weight 1 then with 2 then with 3 

In case of 3 if we consider both edges whose weight is 3 the a cycle is formed so we consider only 1 edge by this we can have 2 Spanning trees with same weights

Spanning tree 1 :

Spanning Tree 2:

Let me know if I'm wrong

by Boss (13.7k points)
edited by
0 votes
Yes, I agree with the claim made and for its proof,

Taking an instance where we have more than one similar edge weights could be the graph (not neccessarily) on which applying kruskal's algo could give us more than one M.S.T's .

NOTE:- The claim holds false everytime we have distinct edge weights.

Let me know if I was wrong.
by (107 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,339 questions
55,765 answers
192,357 comments
90,818 users