prim

prim, a Python code which implements Prim's algorithm to compute a minimal spanning tree of a weighted graph.

For a graph of VN nodes, the algorithm expects to work with a VNxVN weight matrix W, with the properties that:

        W[i,i] = 0
        W[i,j] = W[j,i] for all i, j
        0 < W[i,j] for i and j distinct
        W[i,j] = np.inf if there is no link from node i to node j
      

The algorithm returns an NV-1x2 LINKS array, containing pairs (I,J) representing the links in the spanning tree.

Licensing:

The information on this web page is distributed under the MIT license.

Reference:

1. Robert Sedgewick, Kevin Wayne,
   Algorithms,
   Fourth Edition,
   Addison-Wesley, 2011,
   ISBN13: 978-0321573513.

Source Code:

• prim.py, the source code.
• prim.sh, runs all the tests.
• prim.txt, the output file.