Goals:
Understanding of Kruskal’s algorithm.
Understanding of graphs.
Requirements:
Design, code, and test a C program to determine a Euclidean Minimum Spanning Tree (EMST) for a set of 2-d points interpreted as the vertices of a weighted undirected graph. You may modify http://ranger.uta.edu/~weems/NOTES2320/kruskal.c
Input is to be read from standard input (like the first five assignments):
The first line is one integer value: n, the number of points.
The remaining n lines will each contain two ints defining a point as an x-coordinate and a y-coordinate.
While reading the input, you should echo each point’s position (in the original input sequence), x-coordinate, and y-coordinate.
The edges will be generated by computing the distance between each pair of points as a double. There will be
n
n•(n−1)
=
edges.
2
2
While executing Kruskal’s method, you should indicate the positions of the two points for each edge, the distance between them, and whether the edge is included in the EMST or discarded. Your code may terminate as soon as n-1 edges have been included.
The last output line should give the total weight of the EMST.
Submit your C program on Blackboard 10:45 am (section 004) or 1:45 pm (section 003) on December 4. One of the comment lines should include the compilation command used on OMEGA.
Getting Started:
The total weight for the EMST is unique, but different edges could be chosen based on the order from the preprocessing sort.
