Content deleted Content added
m Maintain {{WPBS}}: 3 WikiProject templates. Remove 1 deprecated parameter: field. Tag: |
|||
| (13 intermediate revisions by 9 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|
{{WikiProject
{{WikiProject
{{WikiProject Computer science |importance=Mid}}
}}
----
== References for the other authors: ==
Line 136 ⟶ 135:
: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)
:::That sounds like a good idea. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 00:54, 24 June 2013 (UTC)
== Pseudocode ==
In my opintion the description given in pseudocode is wrong. It's confsuing when you mix things like that.
it says T is the set of nodes, but later you add edges to it, so you would have maybe in the beginning T = {A, B, C} and after adding edges you'd actually have T = {A, B, C, {A, B}}? That does not cover with what is done in the example.
[[Special:Contributions/141.53.220.30|141.53.220.30]] ([[User talk:141.53.220.30|talk]]) 14:07, 21 July 2013 (UTC)
| |||