Package org.graph4j.spanning

Class PrimMinimumSpanningTree

java.lang.Object

org.graph4j.GraphAlgorithm

org.graph4j.spanning.MinimumSpanningTreeBase

org.graph4j.spanning.PrimMinimumSpanningTree

All Implemented Interfaces:

MinimumSpanningTreeAlgorithm

public class PrimMinimumSpanningTree
extends MinimumSpanningTreeBase

Implementation of Prim's algorithm that uses a binary heap. Complexity O(m + m long n)

Author:

Cristian Frăsinaru

Field Summary

Fields inherited from class org.graph4j.spanning.MinimumSpanningTreeBase

minWeight, tree, treeEdges

Fields inherited from class org.graph4j.GraphAlgorithm

directed, graph

Constructor Summary

Constructors

Constructor	Description
PrimMinimumSpanningTree(Graph graph)

Method Summary

Modifier and Type	Method	Description
protected void	compute()
EdgeSet	getEdges()

Methods inherited from class org.graph4j.spanning.MinimumSpanningTreeBase

getTree, getWeight

Methods inherited from class org.graph4j.GraphAlgorithm

getGraph

Methods inherited from class java.lang.Object

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

Constructor Details

PrimMinimumSpanningTree

public PrimMinimumSpanningTree(Graph graph)

Method Details

getEdges

public EdgeSet getEdges()

Specified by:

getEdges in interface MinimumSpanningTreeAlgorithm

Overrides:

getEdges in class MinimumSpanningTreeBase

Returns:

the edges of the minimum spanning tree.

compute

protected void compute()

Specified by:

compute in class MinimumSpanningTreeBase