Class PrimsMinimumSpanningTree


  • @Reference(authors="R. C. Prim",
               title="Shortest connection networks and some generalizations",
               booktitle="Bell System Technical Journal, 36 (1957)",
               url="https://doi.org/10.1002/j.1538-7305.1957.tb01515.x",
               bibkey="doi:10.1002/j.1538-7305.1957.tb01515.x")
    public class PrimsMinimumSpanningTree
    extends java.lang.Object
    Prim's algorithm for finding the minimum spanning tree.

    Implementation for dense graphs, represented as distance matrix.

    Reference:

    R. C. Prim
    Shortest connection networks and some generalizations
    Bell System Technical Journal 36

    Since:
    0.5.5
    Author:
    Erich Schubert
    • Constructor Detail

      • PrimsMinimumSpanningTree

        public PrimsMinimumSpanningTree()
    • Method Detail

      • processDense

        public static int[] processDense​(double[][] mat)
        Process a k x k distance matrix.
        Parameters:
        mat - Distance matrix
        Returns:
        list of node number pairs representing the edges
      • processDense

        public static <T> int[] processDense​(T data,
                                             PrimsMinimumSpanningTree.Adapter<T> adapter)
        Run Prim's algorithm on a dense graph.
        Parameters:
        data - Data set
        adapter - Adapter instance
        Returns:
        list of node number pairs representing the edges
      • pruneTree

        public static int[] pruneTree​(int numnodes,
                                      int[] tree,
                                      int minDegree)
        Prune the minimum spanning tree, removing all edges to nodes that have a degree below minDegree.
        Parameters:
        numnodes - Number of nodes (MUST use numbers 0 to numnodes-1)
        tree - Original spanning tree
        minDegree - Minimum node degree
        Returns:
        Pruned spanning tree