Package com.jgalgo.alg.span

Interface MinimumSpanningTree

All Known Implementing Classes:
MinimumSpanningTreeAbstract, MinimumSpanningTreeBoruvka, MinimumSpanningTreeFredmanTarjan, MinimumSpanningTreeKargerKleinTarjan, MinimumSpanningTreeKruskal, MinimumSpanningTreePrim, MinimumSpanningTreeYao
public interface MinimumSpanningTree
Minimum spanning tree algorithm.

A spanning tree is an edge sub set of the graph edges which form a tree and connect (span) all the vertices of the graph. A minimum spanning tree (MST) is a spanning tree with the minimum edge weights sum over all spanning trees.

If a maximum spanning tree is needed, the edge weights can be negated and the MST algorithm can be used to compute the maximum spanning tree.

Use newInstance() to get a default implementation of this interface.

Author:
Barak Ugav
See Also:

  • Method Details

    • computeMinimumSpanningTree

      <V, E> MinimumSpanningTree.Result<V,E> computeMinimumSpanningTree(Graph<V,E> g, WeightFunction<E> w)
      Compute the minimum spanning tree (MST) of a given graph.

      If g is an IntGraph, a MinimumSpanningTree.IResult object will be returned. In that case, its better to pass a IWeightFunction as w to avoid boxing/unboxing.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      w - an edge weight function
      Returns:
      a result object containing all the edges of the computed spanning tree, which there are \(n-1\) of them (or less, forming a forest if the graph is not connected)

    • isSpanningTree

      static <V, E> boolean isSpanningTree(Graph<V,E> g, Collection<E> edges)
      Check whether a given set of edges is a spanning tree of a given graph.

      A set of edges is spanning tree if it is a tree and connects all the vertices of the graph. Specifically, if the graph is not empty, the number of edges must be \(n-1\) where \(n\) denote the number of vertices in the graph. The edge set should not contain any duplicate edges.

      If g is an IntGraph, its better to pass a IntCollection as edges to avoid boxing/unboxing.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      edges - a set of edges that should form a spanning tree
      Returns:
      true if the given set of edges is a spanning tree of the given graph, false otherwise

    • isSpanningForest

      static <V, E> boolean isSpanningForest(Graph<V,E> g, Collection<E> edges)
      Check whether a given set of edges is a spanning forest of a given graph.

      A set of edges is spanning forest if it is a forest (do not contains cycles) which connected any pair of vertices that are connected in the original graph, namely its connected components are identical to the connected components of the original graph. Specifically, the number of edges must be \(n-c\) where \(n\) denote the number of vertices in the graph and \(c\) denote the number of connected components in the graph. The edge set should not contain any duplicate edges.

      Type Parameters:
      V - the vertices type
      E - the edges type
      Parameters:
      g - a graph
      edges - a set of edges that should form a spanning forest
      Returns:
      true if the given set of edges is a spanning forest of the given graph, false otherwise

    • newInstance

      static MinimumSpanningTree newInstance()
      Create a new MST algorithm object.

      This is the recommended way to instantiate a new MinimumSpanningTree object.

      Returns:
      a default implementation of MinimumSpanningTree