Borůvka's algorithm: Difference between revisions

Revision as of 14:52, 17 June 2021

Revision as of 17:11, 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 component]]scomponents 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. basedbreaking onties someby [[totalthe order]]object onidentifiers verticesof orthe edges) can be used.

As anAn optimization, we(not couldnecessary for the analysis) is to 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 ==