Content deleted Content added
→Pseudocode: fix vertex names |
→Pseudocode: add correct example |
||
Line 47:
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 {''a'',''b'',''c''} and all edges of weight 1. Then a cycle could be created if we select ''ab'' as the minimal weight edge for {''a''}, ''bc'' for {''b''}, and ''ca'' for {''c''}.
A tie-breaking rule which orders edges first by source, then by destination, will prevent creation of a cycle, resulting in the minimal spanning tree {''ab'', ''bc''}.
'''algorithm''' Borůvka '''is'''
| |||