Revision as of 22:15, 17 June 2021 edit 84.245.120.107 (talk) →Pseudocode: move explanatory text before pseudocode so the pseudocode does not clash with Template:Graph search algorithm ← Previous edit		Revision as of 23:04, 17 June 2021 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,647 edits →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. Next edit →
Line 68: Add its cheapest edge to ''E''' As an optimization, weone could remove from ''G'' each edge that is found to connect two vertices in the same component, so that it does not contribute to the time for searching for cheapest edges in later components. Another optimization would be to keep track of which vertex belongs to which component, and update this information when an edge is added to ''E''', instead of recomputing this information in each iteration of the while loop. == Complexity ==

Borůvka's algorithm: Difference between revisions