Content deleted Content added
→Pseudocode: specify over which edges we're iterating |
→Pseudocode: explain necessity of tie-breaking (after removing requirement of distinct edge weights) |
||
Line 43:
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'''
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 {''u'',''v'',''w''} 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''}.
'''algorithm''' Borůvka '''is'''
'''input:''' A weighted undirected graph ''G'' = (''V'', ''E'').
'''output:''' ''F'',
Initialize a forest ''F'' to (''V'', ''E''') where ''E''' = {}.
| |||