|
== Pseudocode ==
Designating each vertex or set of connected vertices a "[[connected component (graph theory)|component]]", pseudocode for Borůvka's algorithm is:
'''algorithm''' Borůvka '''is'''
Input '''input:''' A graph ''G'' whose edges have distinct weights.
Initialize a forest ''F'' to be a set of one-vertex trees, one for each vertex of the graph.
'''output:''' ''F'' is the minimum spanning forest of ''G''.
While ''F'' has more than one component:
Find the connected components of ''F'' and label each vertex of ''G'' by its component
Initialize thea cheapestforest edge''F'' to be a set of one-vertex trees, one for each componentvertex toof the "None"graph.
For each edge ''uv'' of ''G'':
If ''u'while''' and ''vF'' havehas differentmore than one component labels:'''do'''
If ''uv''Find isthe cheaperconnected thancomponents theof cheapest''F'' edgeand forlabel theeach componentvertex of ''uG'': by its component
Set ''uv'' asInitialize the cheapest edge for theeach component ofto ''u''"None"
If ''uv'for each''' is cheaper than the cheapest edge for the component''uv'' of ''vG'' '''do''':
Set ''uv'if''' as the''u'' cheapest edge for the component ofand ''v'' have different component labels:
'''if''' ''uv'' is cheaper than the cheapest edge for the component of ''u'' '''then'''
For each component whose cheapest edge is not "None": ▼ Add its Set ''uv'' as the cheapest edge tofor the component of ''Fu''
Output: ''F'if''' ''uv'' is cheaper than the minimumcheapest spanningedge forestfor the component of ''Gv'' '''then'''.
Set ''uv'' as the cheapest edge for the component of ''v''
▲ For '''for each ''' component whose cheapest edge is not "None" : '''do'''
Add its cheapest edge to ''F''
If edges do not have distinct weights, then a consistent tie-breaking rule (e.g. breaking ties by the object identifiers of the edges) can be used.
| 