Class MinimumSpanningTree
All methods operate on a WeightedGraph<V, E> whose edges
carry an attribute of type E. The edge attribute is used directly
as the priority key — no separate weight extractor is needed.
Both algorithms require an undirected graph. Calling either on a directed
graph throws IllegalStateException.
Prim result: Map<V, WeightedEdge<V, E>> mapping each
non-source vertex to its cheapest MST edge. The start vertex is absent.
Kruskal result: List<WeightedEdge<V, E>> in non-decreasing
order according to the supplied comparator.
Option 1 example (Double weights):
WeightedGraph<Integer, Double> g = WeightedGraph.undirected();
g.addEdge(new WeightedEdge<>(0, 1, 0.26));
g.addEdge(new WeightedEdge<>(0, 7, 0.16));
Map<Integer, WeightedEdge<Integer, Double>> mst = MinimumSpanningTree.prim(g, 0);
double total = mst.values().stream().mapToDouble(WeightedEdge::attribute).sum();
Option 3 example (custom attribute type):
WeightedGraph<Building, TunnelProperties> g = WeightedGraph.undirected();
g.addEdge(new WeightedEdge<>(b1, b2, tunnelProperties));
Map<Building, WeightedEdge<Building, TunnelProperties>> mst =
MinimumSpanningTree.prim(g, start, Comparator.comparingInt(tp -> tp.cost));
mst.forEach((b, e) -> System.out.println(b + ": cost=" + e.attribute().cost
+ " length=" + e.attribute().length));
-
Method Summary
Modifier and TypeMethodDescriptionstatic <V,E> List <WeightedEdge<V, E>> boruvka(WeightedGraph<V, E> graph, Comparator<E> comparator) Runs Borůvka's algorithm with a custom edge attribute type, ordered by the suppliedComparator.static <V> List<WeightedEdge<V, Double>> boruvka(WeightedGraph<V, Double> graph) Runs Borůvka's algorithm on a graph whose edges carryDoubleweights.static <V,E> List <WeightedEdge<V, E>> kruskal(WeightedGraph<V, E> graph, Comparator<E> comparator) Runs Kruskal's algorithm with a custom edge attribute type, ordered by the suppliedComparator.static <V> List<WeightedEdge<V, Double>> kruskal(WeightedGraph<V, Double> graph) Runs Kruskal's algorithm on a graph whose edges carryDoubleweights.static <V,E> Map <V, WeightedEdge<V, E>> prim(WeightedGraph<V, E> graph, V start, Comparator<E> comparator) Runs Prim's algorithm with a custom edge attribute type, ordered by the suppliedComparator.static <V> Map<V, WeightedEdge<V, Double>> prim(WeightedGraph<V, Double> graph, V start) Runs Prim's algorithm on a graph whose edges carryDoubleweights.
-
Method Details
-
prim
Runs Prim's algorithm on a graph whose edges carryDoubleweights.Edge attributes are compared by natural
Doubleordering. No configuration required.- Type Parameters:
V- the vertex type.- Parameters:
graph- an undirectedWeightedGraph<V, Double>.start- the source vertex (absent from the result).- Returns:
- the MST as
Map<V, WeightedEdge<V, Double>>. - Throws:
IllegalStateException- ifgraphis directed.
-
prim
public static <V,E> Map<V,WeightedEdge<V, primE>> (WeightedGraph<V, E> graph, V start, Comparator<E> comparator) Runs Prim's algorithm with a custom edge attribute type, ordered by the suppliedComparator.The edge attribute is used directly as the priority key. No weight extractor is needed.
- Type Parameters:
V- the vertex type.E- the edge attribute type.- Parameters:
graph- an undirectedWeightedGraph<V, E>.start- the source vertex (absent from the result).comparator- orders edge attributes.- Returns:
- the MST as
Map<V, WeightedEdge<V, E>>. - Throws:
IllegalStateException- ifgraphis directed.
-
kruskal
Runs Kruskal's algorithm on a graph whose edges carryDoubleweights.Edges are sorted by natural
Doubleordering. The returned list is in non-decreasing weight order.- Type Parameters:
V- the vertex type.- Parameters:
graph- an undirectedWeightedGraph<V, Double>.- Returns:
- the MST as
List<WeightedEdge<V, Double>>in non-decreasing weight order. - Throws:
IllegalStateException- ifgraphis directed.
-
kruskal
public static <V,E> List<WeightedEdge<V,E>> kruskal(WeightedGraph<V, E> graph, Comparator<E> comparator) Runs Kruskal's algorithm with a custom edge attribute type, ordered by the suppliedComparator.The edge attribute is used directly as the sort key. The returned list is in non-decreasing order according to
comparator.- Type Parameters:
V- the vertex type.E- the edge attribute type.- Parameters:
graph- an undirectedWeightedGraph<V, E>.comparator- orders edge attributes.- Returns:
- the MST as
List<WeightedEdge<V, E>>in non-decreasing order. - Throws:
IllegalStateException- ifgraphis directed.
-
boruvka
Runs Borůvka's algorithm on a graph whose edges carryDoubleweights.Edges are compared by natural
Doubleordering. The returned list contains exactly N-1 edges for a connected graph of N vertices.- Type Parameters:
V- the vertex type.- Parameters:
graph- an undirectedWeightedGraph<V, Double>.- Returns:
- the MST as
List<WeightedEdge<V, Double>>. - Throws:
IllegalStateException- ifgraphis directed.
-
boruvka
public static <V,E> List<WeightedEdge<V,E>> boruvka(WeightedGraph<V, E> graph, Comparator<E> comparator) Runs Borůvka's algorithm with a custom edge attribute type, ordered by the suppliedComparator.The edge attribute is used directly as the sort key. The returned list contains exactly N-1 edges for a connected graph of N vertices.
- Type Parameters:
V- the vertex type.E- the edge attribute type.- Parameters:
graph- an undirectedWeightedGraph<V, E>.comparator- orders edge attributes.- Returns:
- the MST as
List<WeightedEdge<V, E>>. - Throws:
IllegalStateException- ifgraphis directed.
-