Content deleted Content added
→Pseudocode: add correct example |
→Pseudocode: add tie-breaking rule explicitly into the pseudocode |
||
Line 55:
Initialize a forest ''F'' to (''V'', ''E''') where ''E''' = {}.
''completed'' := '''false'''
'''while''' not ''completed'' '''do'''
Find the [[Component_(graph_theory)|connected component]]s of ''F'' and assign to each vertex its component
Initialize the cheapest edge for each component to "None"
'''for each''' edge ''uv'' in ''E'', where ''u'' and ''v'' are in different components of ''F'':
'''if''' is-preferred-over(''uv'', ''wx'') '''then'''
Set ''uv'' as the cheapest edge for the component of ''u''
'''if''' is-preferred-over(''uv'', ''yz'') '''then'''
Set ''uv'' as the cheapest edge for the component of ''v''
'''if''' all components have cheapest edge set to "None" '''then'''
''// no more trees can be merged -- we are finished''
''completed'' := '''true'''
'''else'''
''completed'' := '''false'''
'''for each''' component whose cheapest edge is not "None" '''do'''
Add its cheapest edge to ''E'''
'''function''' is-preferred-over(''edge1'', ''edge2'') '''is'''
'''return''' (''edge1'' is "None") or
(weight(''edge1'') < weight(''edge2'')) or
(weight(''edge1'') = weight(''edge2'') and tie-breaking-rule(''edge1'', ''edge2''))
'''function''' tie-breaking-rule(''edge1'', ''edge2'') '''is'''
The tie-breaking rule; returns '''true''' if and only if ''edge1''
is preferred over ''edge2'' in the case of a tie.
As an optimization, one could remove from ''G'' each edge that is found to connect two vertices in the same component, so that it does not contribute to the time for searching for cheapest edges in later components.
| |||