Borůvka's algorithm: Revision history

27 March 2025

• curprev 14:5414:54, 27 March 2025 Patrick Welsh talk contribs m 11,258 bytes −61 RCP reverted edits by 186.185.247.155 (Talk); changed back to last revision by JJMC89 bot III: Unconstructive edit undo Tag: Rollback
• curprev 12:2012:20, 27 March 2025 186.185.247.155 talk 11,319 bytes +37 →Pseudocode: Fails undo Tags: Reverted Mobile edit Mobile web edit
• curprev 12:1912:19, 27 March 2025 186.185.247.155 talk 11,282 bytes +24 →Pseudocode: Fails undo Tags: Reverted Mobile edit Mobile web edit

12 October 2024

• curprev 19:5419:54, 12 October 2024 JJMC89 bot III talk contribs m 11,258 bytes −10 Moving Category:Algorithms in graph theory to Category:Graph algorithms per Wikipedia:Categories for discussion/Log/2024 October 4 undo Tag: Manual revert
• curprev 02:2102:21, 12 October 2024 JJMC89 bot III talk contribs m 11,268 bytes +10 Moving Category:Graph algorithms to Category:Algorithms in graph theory per Wikipedia:Categories for discussion/Log/2024 October 4#Category:Graph algorithms undo Tag: Reverted

11 March 2024

• curprev 17:5517:55, 11 March 2024 Beland talk contribs m 11,258 bytes +8 convert special characters found by Wikipedia:Typo Team/moss (via WP:JWB) undo

4 November 2023

• curprev 06:1706:17, 4 November 2023 Tapir1729 talk contribs 11,250 bytes +20 →Other algorithms undo

13 October 2023

• curprev 06:0706:07, 13 October 2023 Catttte talk contribs m 11,230 bytes −35 u → ů undo Tag: 2017 wikitext editor

16 June 2023

• curprev 15:4215:42, 16 June 2023 Headbomb talk contribs 11,265 bytes 0 ce undo

27 February 2023

• curprev 23:3123:31, 27 February 2023 Vozul talk contribs 11,265 bytes +32 added new navbox undo
• curprev 19:4019:40, 27 February 2023 Vozul talk contribs 11,233 bytes +227 added infobox, fixed formatting in →Complexity undo

19 April 2022

• curprev 18:1718:17, 19 April 2022 David Eppstein talk contribs 11,006 bytes −28 remove bad navbox undo

28 January 2022

• curprev 16:4216:42, 28 January 2022 David Eppstein talk contribs 11,034 bytes −13 tighter shortdesc undo
• curprev 14:2114:21, 28 January 2022 Lollipoplollipoplollipop talk contribs 11,047 bytes +77 Adding local short description: "Algorithm for finding minimum spanning tree of a graph", overriding Wikidata description "algorithm for finding minimum spanning trees by repeatedly finding the shortest edge out of each subtree in a forest and adding all such edges to the forest" (Shortdesc helper) undo

27 January 2022

• curprev 15:4115:41, 27 January 2022 141.76.27.151 talk 10,970 bytes 0 →Pseudocode: fix typo, we prefer edge1 over edge2 if the latter one is None, not the first one. undo

7 December 2021

• curprev 19:3419:34, 7 December 2021 David Eppstein talk contribs m 10,970 bytes +1 Reverted edits by Tinaleo68 (talk) to last version by Citation bot undo Tag: Rollback
• curprev 14:3714:37, 7 December 2021 Tinaleo68 talk contribs 10,969 bytes −1 →Example undo Tag: Reverted

14 November 2021

• curprev 07:1107:11, 14 November 2021 Citation bot talk contribs 10,970 bytes +92 Add: s2cid, doi, issue. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar undo

18 June 2021

• curprev 01:0201:02, 18 June 2021 84.245.120.107 talk 10,878 bytes +534 →Pseudocode: add tie-breaking rule explicitly into the pseudocode undo
• curprev 00:4700:47, 18 June 2021 84.245.120.107 talk 10,344 bytes +168 →Pseudocode: add correct example undo
• curprev 00:4500:45, 18 June 2021 84.245.120.107 talk 10,176 bytes 0 →Pseudocode: fix vertex names undo
• curprev 00:4400:44, 18 June 2021 84.245.120.107 talk 10,176 bytes +489 →Pseudocode: explain necessity of tie-breaking (after removing requirement of distinct edge weights) undo

17 June 2021

• curprev 23:5323:53, 17 June 2021 84.245.120.107 talk 9,687 bytes +18 →Pseudocode: specify over which edges we're iterating undo
• curprev 23:0423:04, 17 June 2021 David Eppstein talk contribs 9,669 bytes −128 →Pseudocode: Here's the reason I am removing this 2nd opt as original research, again: I still don't see how it helps. Maintaining components dynamically when each edge is added doesn't help, because we don't need that information until the next interation when we have plenty of time to recompute. And it does hurt, because even with union-find dynamic connectivity is not a constant-time operation. undo
• curprev 22:1522:15, 17 June 2021 84.245.120.107 talk 9,797 bytes +85 →Pseudocode: move explanatory text before pseudocode so the pseudocode does not clash with Template:Graph search algorithm undo
• curprev 22:1022:10, 17 June 2021 84.245.120.107 talk 9,712 bytes +345 →Pseudocode: re WP:OR - mea culpa, I misread the original paragraph about optimization; adding this more neutral formulation of my original suggestion which is hopefully not considered OR undo
• curprev 20:4720:47, 17 June 2021 84.245.120.107 talk 9,367 bytes −101 →Complexity: admittedly m < n is quite an uncommon case undo
• curprev 20:3520:35, 17 June 2021 84.245.120.107 talk 9,468 bytes +128 →Complexity: complexity is not "obviously correct" undo
• curprev 20:2920:29, 17 June 2021 84.245.120.107 talk 9,340 bytes +28 →Pseudocode: specify that E' is initially empty undo
• curprev 20:2120:21, 17 June 2021 84.245.120.107 talk 9,312 bytes +25 →Pseudocode: unambiguous wikilink undo
• curprev 20:1820:18, 17 June 2021 84.245.120.107 talk 9,287 bytes −360 →Pseudocode: removing the "orignal research" (a.k.a common sense), as well as the previously-present instance thereof undo
• curprev 20:1820:18, 17 June 2021 84.245.120.107 talk 9,647 bytes +57 Undid revision 1029061107 by David Eppstein (talk) undo Tag: Undo
• curprev 17:1117:11, 17 June 2021 David Eppstein talk contribs 9,590 bytes −57 Undid revision 1029041621 by 84.245.120.107 (talk) WP:OR undo Tags: Undo Reverted
• curprev 14:5214:52, 17 June 2021 84.245.120.107 talk 9,647 bytes +57 →Pseudocode: improve presentation + add idea of a (very simple and effective) optimization undo Tag: Reverted
• curprev 14:4714:47, 17 June 2021 84.245.120.107 talk 9,590 bytes +70 →Pseudocode: make more readable undo

14 May 2021

• curprev 13:5413:54, 14 May 2021 Jdgilbey talk contribs 9,520 bytes +286 →Pseudocode: Modify the code so it doesn't fall into an infinite loop if the graph G is not connected undo

10 January 2021

• curprev 13:2813:28, 10 January 2021 Monkbot talk contribs m 9,234 bytes −64 Task 18 (cosmetic): eval 11 templates: hyphenate params (4×); del |postscript= (2×); cvt lang vals (6×); undo Tag: AWB

12 September 2020

• curprev 04:3604:36, 12 September 2020 2601:c0:c300:7e60:a05e:8269:ffbb:a679 talk 9,298 bytes −4 →Complexity undo Tag: Manual revert
• curprev 04:2204:22, 12 September 2020 2601:c0:c300:7e60:a05e:8269:ffbb:a679 talk 9,302 bytes +4 →Complexity undo

19 August 2020

• curprev 18:0818:08, 19 August 2020 David Eppstein talk contribs 9,298 bytes −6 Undid revision 973866839 by 2602:306:3346:4510:BC77:9977:F0DE:ECAB (talk) inappropriate boldface, and it is not completely trivial that the edge chosen by one component equals the edge chosen by the other (it needs a consistent tie-breaking rule) undo Tag: Undo
• curprev 18:0018:00, 19 August 2020 2602:306:3346:4510:bc77:9977:f0de:ecab talk 9,304 bytes +6 "These happen to be the same edge." This sentence should be removed, since with two components left they must be the same edge. undo

10 June 2020

• curprev 18:2318:23, 10 June 2020 WOSlinker talk contribs m 9,298 bytes −37 border/cellpadding/cellspacing not needed due to wikitable class undo

22 May 2020

• curprev 15:0915:09, 22 May 2020 95.168.116.30 talk 9,335 bytes −40 As described in the Pseudocode section, in case of equal weights we need a trivial modification to the algorithm. Many other graph algorithms similarly don't work as given when some edges are equal, but consistent tie-breaking is always assumed. There is no need to confuse people in the first sentence of the article. undo

14 April 2020

• curprev 03:2603:26, 14 April 2020 OAbot talk contribs m 9,375 bytes +49 Open access bot: hdl added to citation with #oabot. undo

17 December 2019

• curprev 11:1711:17, 17 December 2019 Frap talk contribs 9,326 bytes +218 →Pseudocode: MOS:ALGO undo

24 June 2019

• curprev 10:4010:40, 24 June 2019 Smclemon talk contribs m 9,108 bytes −3 fix indentation for final three lines of the pseudocode version - they were aligned half-way between the other levels of indentation undo

7 February 2019

• curprev 09:3609:36, 7 February 2019 Citation bot talk contribs m 9,111 bytes +77 Alter: journal. Add: citeseerx. | You can use this bot yourself. Report bugs here. | User-activated. undo

18 October 2018

• curprev 09:5609:56, 18 October 2018 178.197.225.246 talk 9,034 bytes +6 No mention of greedyness anywhere, while Kruskal article has it. Editing to make it more obvious. undo

12 April 2018

• curprev 04:4504:45, 12 April 2018 David Eppstein talk contribs 9,028 bytes +2 or actually I think Georges undo
• curprev 04:4404:44, 12 April 2018 David Eppstein talk contribs 9,026 bytes −14 In fact it appears to be that he was a Frenchman named Georges Sollin; see e.g. https://books.google.com/books?id=rmYpBgAAQBAJ&pg=PA169 undo