Content deleted Content added
Line 135:
[[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)
::Thanks for the counter-example! I now see the need of distinctness: in step 7, if there are two edges with the same weight connecting two components, they might both get added to T under different components. If I may, I would like to add a short explanation for the necessity of the constraint after the pseudo-code. [[User:Falcongl|Falcongl]] ([[User talk:Falcongl|talk]]) 23:07, 23 June 2013 (UTC)
| |||