Content deleted Content added
→Complexity: admittedly m < n is quite an uncommon case |
→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 |
||
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.
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 ==
| |||