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

Revision as of 19:25, 14 July 2017

Latest revision as of 23:37, 8 March 2024

(4 intermediate revisions by 4 users not shown)

Line 1:

{{WikiProject banner shell|class=C|

{{WikiProjectBannerShell|1=

{{Maths rating |class=CWikiProject Mathematics|priority=Low |field=discrete}}

{{WikiProject Computing |class=C |importance=Low}}

{{WikiProject Computer science |class=C |importance=Mid}}

}}

----

Line 143 ⟶ 142:

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)

== Current pseudocode assumes connected graph ==

Borůvka's algorithm is in many cases presented in a variant, which works for disconnected graphs and generates a minimum spanning forest, by presenting it using the edge contractions. But the pseudocode assumes, that the graph is connected by saying:

<source lang="text" start="2" line>

While T has more than one component:

</source>

I believe this should read:

<source lang="text" start="2" line>

While there is an edge between any two components:

</source>

Although it is possible, that the original paper covers only the connected case.