Borůvka's algorithm: Difference between revisions

Revision as of 17:11, 17 June 2021

Revision as of 20:18, 17 June 2021

Line 40:

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

Line 49:

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

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

Find the [[connected componentscomponent]]s of ''F'' and assign to each vertex its component

Initialize the cheapest edge for each component to "None"

'''for each''' edge ''uv'' where ''u'' and ''v'' are in different components:

Line 65:

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 can be used (e.g. breakingbased tieson bysome the[[total objectorder]] identifierson ofvertices theor edges) can be used.

AnAs an optimization, (notwe necessary for the analysis) is tocould remove from ''G'' each edge that is found to connect two vertices in the same component as each other.

An even more important optimization would be to keep track of which vertex belongs to which component, and update this information when an edge is added to ''E''', instead of recomputing this information in each iteration of the while loop.

== Complexity ==