Revision as of 20:18, 17 June 2021 edit 84.245.120.107 (talk) Undid revision 1029061107 by David Eppstein (talk) Tag: Undo ← Previous edit		Revision as of 20:18, 17 June 2021 edit undo 84.245.120.107 (talk) →Pseudocode: removing the "orignal research" (a.k.a common sense), as well as the previously-present instance thereof Next edit →
Line 66: In the conditional clauses, every edge ''uv'' is considered cheaper than "None". The purpose of the ''completed'' variable is to determine whether the forest ''F'' is yet a spanning forest. If edges do not have distinct weights, then a consistent tie-breaking rule can be used (e.g. based on some [[total order]] on vertices or edges). ~~As an optimization, we could remove from ''G'' each edge that is found to connect two vertices in the same component.~~ An even more important 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