MinimumSpanningTreePrim (JGAlgo - Parent 0.5.1-SNAPSHOT API)

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 Detail
  - MinimumSpanningTreePrim
```
public MinimumSpanningTreePrim()
```
    Construct a new MST algorithm object.
    Please prefer using MinimumSpanningTree.newInstance() to get a default implementation for the MinimumSpanningTree interface.