Package org.graph4j.spanning

Class BoruvkaMinimumSpanningTreeDefault

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.spanning.MinimumSpanningTreeBase

org.graph4j.spanning.BoruvkaMinimumSpanningTreeBase

org.graph4j.spanning.BoruvkaMinimumSpanningTreeDefault

All Implemented Interfaces:

MinimumSpanningTreeAlgorithm

public class BoruvkaMinimumSpanningTreeDefault
extends BoruvkaMinimumSpanningTreeBase

Boruvka algorithm for finding a minimum spanning tree. You can see more : https://en.wikipedia.org/wiki/Bor%C5%AFvka%27s_algorithm

Author:

Sorodoc Cosmin

Field Summary

Fields inherited from class org.graph4j.spanning.BoruvkaMinimumSpanningTreeBase

cheapest, uf

Fields inherited from class org.graph4j.spanning.MinimumSpanningTreeBase

minWeight, tree, treeEdges

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
BoruvkaMinimumSpanningTreeDefault(Graph graph)

Method Summary

Modifier and Type	Method	Description
protected boolean	updateCheapestEdges()	For each component, find the smallest weighted edge and update the cheapest array

Methods inherited from class org.graph4j.spanning.BoruvkaMinimumSpanningTreeBase

compute

Methods inherited from class org.graph4j.spanning.MinimumSpanningTreeBase

getEdges, getTree, getWeight

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

BoruvkaMinimumSpanningTreeDefault

public BoruvkaMinimumSpanningTreeDefault(Graph graph)

Method Details

updateCheapestEdges

protected boolean updateCheapestEdges()

For each component, find the smallest weighted edge and update the cheapest array

Specified by:

updateCheapestEdges in class BoruvkaMinimumSpanningTreeBase

Returns:

true if there is at least one outgoing edge from the components, false otherwise