Content deleted Content added
→Pseudocode: explain necessity of tie-breaking (after removing requirement of distinct edge weights) |
→Pseudocode: fix vertex names |
||
Line 46:
If edges do not have distinct weights, then a consistent '''tie-breaking rule''' must be used, e.g. based on some [[total order]] on vertices or edges.
This can be achieved by representing vertices as integers and comparing them directly; comparing their [[memory address]]es; etc.
A tie-breaking rule is necessary to ensure that the created graph is indeed a forest, that is, it does not contain cycles. For example, consider a triangle graph with nodes {''
'''algorithm''' Borůvka '''is'''
| |||