Content deleted Content added
Line 134:
Observe that none of the steps in the algorithm depends on the constraint that the edge weights are distinct in the graph. I suggest to remove that assumption and edit the content accordingly, i.e. the MST might not be unique.
[[User:Falcongl|Falcongl]] ([[User talk:Falcongl|talk]]) 20:37, 23 June 2013 (UTC)
:If the edge weights are not distinct then the algorithm can easily create cycles. E.g. suppose that the graph consists of three vertices a, b, and c, and three edges forming a triangle with all edge weights one. Then, suppose that a picks b as its nearest neighbor, b picks c, and c picks a. The result is not a tree. This can be fixed by using an appropriate tie-breaking rule, but that's essentially the same thing as forcing all edge weights to be distinct. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 20:48, 23 June 2013 (UTC)
| |||