Class KruskalMinimumSpanningTree<V,W>

java.lang.Object

org.episteme.core.mathematics.discrete.KruskalMinimumSpanningTree<V,W>

All Implemented Interfaces:

MinimumSpanningTree<V,W>

public class KruskalMinimumSpanningTree<V,W>
extends Object
implements MinimumSpanningTree<V,W>

Kruskal's algorithm for finding Minimum Spanning Tree.

Alternative to Prim's algorithm. Sorts edges by weight and greedily adds them if they don't create a cycle. Uses Union-Find data structure. O(E log E) time.

*

Reference:
Kruskal, J. B. (1956). On the shortest spanning subtree of a graph and the traveling salesman problem. Proceedings of the American Mathematical Society, 7(1), 48-50.

Since:

1.0

Author:

Silvere Martin-Michiellot, Gemini AI (Google DeepMind)

Constructor Summary

Constructors

Constructor	Description
KruskalMinimumSpanningTree(GraphWeightAdapter<W> weightAdapter)

Method Summary

Modifier and Type	Method	Description
Set<WeightedEdge<V,W>>	findMST(WeightedGraph<V,W> graph)	Finds the Minimum Spanning Tree of the given graph.
static <V> KruskalMinimumSpanningTree<V,Double>	ofDouble()
static <V> KruskalMinimumSpanningTree<V,Real>	ofReal()

Methods inherited from class Object

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

Constructor Details

KruskalMinimumSpanningTree

public KruskalMinimumSpanningTree(GraphWeightAdapter<W> weightAdapter)

Method Details

ofDouble

public static <V>
KruskalMinimumSpanningTree<V,Double> ofDouble()

ofReal

public static <V>
KruskalMinimumSpanningTree<V,Real> ofReal()

findMST

public Set<WeightedEdge<V,W>> findMST(WeightedGraph<V,W> graph)

Description copied from interface: MinimumSpanningTree

Finds the Minimum Spanning Tree of the given graph.

Specified by:

findMST in interface MinimumSpanningTree<V,W>

Parameters:

graph - the graph to find the MST for

Returns:

a set of edges representing the MST