Editing Borůvka's algorithm (section)

== 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''' 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 {''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'''
     '''input:''' A weighted undirected graph ''G'' = (''V'', ''E'').
     '''output:''' ''F'', a minimum spanning forest of ''G''.
 
     Initialize a forest ''F'' to (''V'', ''{{prime|E}}'') where ''{{prime|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'':
             let ''wx'' be the cheapest edge for the component of ''u''
             '''if''' is-preferred-over(''uv'', ''wx'') '''then'''
                 Set ''uv'' as the cheapest edge for the component of ''u''
             let ''yz'' be the cheapest edge for the component of ''v''
             '''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''' (''edge2'' 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.