Content deleted Content added
→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 |
→Pseudocode: move explanatory text before pseudocode so the pseudocode does not clash with Template:Graph search algorithm |
||
Line 40:
== Pseudocode ==
The following pseudocode illustrates a basic implementation of Borůvka's algorithm.
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).▼
'''algorithm''' Borůvka '''is'''
Line 63 ⟶ 67:
'''for each''' component whose cheapest edge is not "None" '''do'''
Add its cheapest edge to ''E'''
▲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.
| |||