Kruskal's algorithm begins with an empty set of edges and repeats one simple step: amongst all edges whose addition to would not create a cycle, add one of mimimum weight to . We continue until it is no longer possible to do so, i.e. when all edges in () would, if added to , create a cycle with the edges already in . At that point we have a subset () that is maximal with respect to the property of being acyclic, which implies that = ((), ) is a spanning tree in (see the "treeness" theorem in the handout on Graph Theory.) It's proved in the same handout that necessarily || = |()| 1. Section 23.1 of CLRS establishes that is in fact a MWST.

Sort the edges of by increasing weights, then step through the list, marking those edges whose addition will not create a cycle with those previously marked. We obtain

Edge: (, ), (, ), (, ), (, ), (, ), (5, 7), (, ), (5, 6), (4, 5), (2, 5), (4, 6)

Weight: 1 2 3 4 5 5 6 6 7 8 9

where we have bolded the marked edges. Therefore = {(3,5),(6,7),(1,4),(3,7),(2,3),(1,2)}, and = ( {1, 2, 3, 4, 5, 6, 7}, ) has weight () = 21. Further inspection shows that, although this graph has many spanning trees, this is its only minimum weight spanning tree.

This executable will take two command line arguments giving the names two files which store program input and output, and whose format is described below. Upon doing the Unix command

$ MWST input_file output_file

your program will read input_file, solve the MWST problem for the connected weighted graph it encodes, and create output_file containing the solution.

The first two lines of an input file will contain single integers and , giving the number of vertices and the number of edges in , respectively. The vertices will be labeled by the set = {1, 2, 3, ... , }. The next lines will each contain two integers (vertex labels) and one real number, separated by spaces, giving the end vertices and weight of an edge in . The edge labels will be determined by the position of an edge in this list. In general, a triple , , on line + 2 defines an edge with label (for 1 ).

Each of the + 2 lines of the input file will end in a Unix newline character. The following example defines the weighted graph.

7

11

1 2 6

1 4 3

2 3 5

2 5 8

3 5 1

3 7 4

4 5 7

4 6 9

5 6 6

5 7 5

6 7 2

An output file will contain lines. The first 1 lines will give the edges of an MWST in the following format.

label: (end1, end2) weight

These edges will be given in sorted order (smallest to largest) by edge weight. The last line will give the total weight of the spanning tree. A possible output file for the above example is then

5: (3, 5) 1.0

11: (6, 7) 2.0

2: (1, 4) 3.0

6: (3, 7) 4.0

3: (2, 3) 5.0

1: (1, 2) 6.0

Total Weight = 21.00

Note that a valid output file for this project is not unique, since there may be more than one MWST for a given graph. Also the pair (, ) denotes an un-orded pair which could also be specified as (, ). Other than these variations, an output file must match the above format exactly. In particular the label will be right justified in a field of width 4, followed by a colon, then a space, then (, ) or (, ), then the weight rounded to one decimal place. The last line will begin at column 1, and the weight will be rounded to 2 decimal places.

The program will be written in Java.