Package com.jgalgo.alg.span

Class MinimumSpanningTreePrim

java.lang.Object

com.jgalgo.alg.span.MinimumSpanningTreeAbstract

com.jgalgo.alg.span.MinimumSpanningTreePrim

All Implemented Interfaces:

MinimumSpanningTree

public class MinimumSpanningTreePrim
extends MinimumSpanningTreeAbstract

Prim's minimum spanning tree algorithm.

The algorithm maintain a tree and repeatedly adds the lightest edge that connect a vertex from tree to the reset of the vertices. The algorithm is similar to Dijkstra shortest paths algorithm in its idea, and it also uses a heap that is updated using decreaseKey().

The running time of Prim's algorithm is \(O(m + n \log n)\) and it uses linear space. It's running time is very good it practice and can be used as a first choice for MinimumSpanningTree algorithm. Note that only undirected graphs are supported.

Based on "Shortest connection networks And some generalizations" by Prim, R. C. (1957).

Author:

Barak Ugav

See Also:

• Wikipedia

Nested Class Summary

Nested classes/interfaces inherited from interface com.jgalgo.alg.span.MinimumSpanningTree

MinimumSpanningTree.IResult, MinimumSpanningTree.Result<V,E>

Constructor Summary

Constructors

Constructor	Description
MinimumSpanningTreePrim()	Construct a new MST algorithm object.

Method Summary

Methods inherited from class com.jgalgo.alg.span.MinimumSpanningTreeAbstract

computeMinimumSpanningTree

Methods inherited from class java.lang.Object

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

Constructor Details

MinimumSpanningTreePrim

public MinimumSpanningTreePrim()

Construct a new MST algorithm object.

Please prefer using MinimumSpanningTree.newInstance() to get a default implementation for the MinimumSpanningTree interface.