Borůvka's algorithm: Difference between revisions

Revision as of 13:54, 14 May 2021

Revision as of 14:47, 17 June 2021

Line 42:

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:''' A weighted undirected graph ''G'' whose= edges have(''V'', distinct weights''E'').

'''output:''' ''F'' is, the minimum spanning forest of ''G''.

Initialize a forest ''F'' to be a set of one-vertex trees(''V'', one for each vertex of the graph''E''').

''completed'' = '''false'''

'''while''' not ''completed'' '''do'''

Find the connected components of ''F'' and labelassign to each vertex of ''G'' by its component

Initialize the cheapest edge for each component to "None"

'''for each''' edge ''uv'' of where ''Gu'' and '''do'v'' are in different components:

'''if''' ''uuv'' andis ''v''cheaper havethan differentthe cheapest edge for the component labels:of ''u'' '''then'''

'''if'''Set ''uv'' is cheaper thanas the cheapest edge for the component of ''u'' '''then'''

Set'''if''' ''uv'' asis cheaper than the cheapest edge for the component of ''uv'' '''then'''

'''if'''Set ''uv'' is cheaper thanas the cheapest edge for the component of ''v'' '''then'''

Set ''uv'if''' asall thecomponents have cheapest edge forset theto component of"None" ''v'then'''

''// no more trees can be merged -- we are finished''

''completed'' = '''true'''

''completed'for each''' component whose cheapest edge is not "None"= '''dotrue'''

Add its cheapest edge to ''F'else'''

''completed'' = '''false'''

'''for each''' component whose cheapest edge is not "None" '''do'''

Add its cheapest edge to ''E'''

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.