Minimum Spanning Tree Algorithm

Download

Download jar file or use maven. psjava requires Java 1.6 (or above)

<dependency>
    <groupId>org.psjava</groupId>
    <artifactId>psjava</artifactId>
    <version>0.1.19</version>
</dependency>

Example Code

MutableUndirectedWeightedGraph<String, Integer> graph = MutableUndirectedWeightedGraph.create();
graph.insertVertex("A");
graph.insertVertex("B");
graph.insertVertex("C");
graph.addEdge("A", "B", 100);
graph.addEdge("A", "C", 10);
graph.addEdge("B", "C", 20);

MinimumSpanningTreeAlgorithm algorithm = GoodMinimumSpanningTreeAlgorithm.getInstance();
Collection<UndirectedWeightedEdge<String, Integer>> tree = algorithm.calc(graph, IntegerNumberSystem.getInstance());

int sum = 0;
for (UndirectedWeightedEdge<String, Integer> e : tree)
	sum += e.weight();
// sum must be 10+20=30

See Also

• Prim Algorithm
• Kruscal Algorithm

---

Copyright 2014 psjava team. View on GitHub