Talk:Borůvka's algorithm: Difference between revisions

Revision as of 20:37, 23 June 2013

Latest revision as of 23:37, 8 March 2024

(15 intermediate revisions by 10 users not shown)

Line 1:

{{WikiProject banner shell|class=C|

{{maths rating|class=Start|priority=Low|field=discrete}}

{{WikiProject ComputingMathematics|class=Start|importancepriority=Low }}

{{WikiProject ComputerComputing science|importance=Low}}

{{WikiProject Computer science |importance=Mid}}

|class=Start

|importance=Mid

}}

----

== References for the other authors: ==

Line 134 ⟶ 133:

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)

::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)