kruskal

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

For a graph of VN nodes and EN edges, the algorithm expects to work with a ENx3 EDGES array, with each row containing values W, I, J, representing the weight and two end nodes of an edge.

The algorithm returns an (VN-1)x3 LINKS array, listing triples (W,I,J) representing the weight and links of the edges forming the spanning tree.

Licensing:

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

Reference:

1. Joseph Kruskal,
   On the shortest spanning subtree of a graph and the traveling salesman problem,
   Proceedings of the American Mathematical Society,
   Volume 7, Number 1, pages 48-50, 1956.

Source Code:

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