使用Ｃ语言写一个Minimum Spanning Tree.

In Assignment #1, your program can successfully read in an input ﬁle that describes n = NUM PT points in the two-dimensional plane, within the rectangular area [0, MAX X] × [0, MAX Y]. Your program for Assignment #2 computes a minimum-weight spanning tree (MST) for these n points. By executing the following command,

>myprogram -i instance10 001.txt i i∗ d(i, i∗)

your program appends the edges of the MST to the input ﬁle instance10 001.txt, one in a line as:

where pi and pi∗ are the two end points of the edge, pi is the parent of pi∗, and d(i, i∗) is the weight of the edge (the distance between the two points).

The goal of Assignment #3 is to lay down the edges of the MST to achieve the maximum total overlap, and to conduct numerical experiments to collect the statistics (Lecture slide set #11 contains some illustration). The following list contains the speciﬁcations for Assignment #3 (10 marks in total):

1. Using the following command to run your program for Assignment #3,

>myprogram -i instance10 002.txt [-o output10 002.txt]

Here the input ﬁle instance10 002.txt is in the format resulted from Assignment #2 (provided as the sample input in eClass), that is, it contains the edges of the MST.

The option “-o output10 002.txt” speciﬁes a ﬁle to write the program output; if it is not there, your program writes output to stdout data stream.

2. The following data type is strongly recommended to be used in your program; the subsequent des- cription is based on this struct:

struct point {

int index;

int x;

int y;

int parent;

int num_children;

int child[8];

int overlap_hv;

int overlap_vh;

Essentially, this new data type is for storing information associated with a point, which has a number of entries and their meanings. In particular, it is guaranteed that the number of child- ren num children one can have is at most 8; the member ‘overlap hv’ records the total overlap of the subtree rooted at the edge (parent, index) when the edge (parent, index) is laid as an L-shape ﬁrst horizontally out of parent then vertically to reach index (that is, parent is incident at the horizontal portion of the edge and i is incident at the vertical portion of the edge; in the degenerate case, the horizontal portion or the vertical portion of the edge has length 0).

When a variable of struct point is declared, all its members are initialized to −1, indicating invalid values, except .num children initialized to 0.

In the sequel, assume you declare the following array to store the n points:

struct point p[n];

3. Assume the ﬁrst given point in the instance ﬁle has index/subscript 0 (that is, p[0] is the root of the MST). If n = 1, your program terminates without doing anything; otherwise (i.e., n > 1), your program prints to the output the values of all the members for the second point (i.e., p[1]), one in a line. For the member array .child, you only need to print out the children that are ≥ 0. These form the ﬁrst set of lines in the output; print an empty line after them.

Using the sample input ﬁle instance10 002.txt, your program should print the following out:

p[1].index = 1;

p[1].x = 0;

p[1].y = 90;

p[1].parent = 5;

p[1].num_children = 0;

p[1].child[8] = {};

p[1].overlap_hv = 0;

p[1].overlap_vh = 0;

4. Starting with the root of the MST, your program prints to the output the following members in one line: .index, .num children, .child[0], . . ., .child[.num children - 1]

Then recursively prints the same information for each child. These form the second set of lines in the output; print an empty line after them.

(This is the depth-ﬁrst-search order of the points, or the DFS order.)

Using the sample input ﬁle instance10 002.txt, your program should print the following out:

p[0].index = 0, .num_children = 1, .child[0] = 9

p[9].index = 9, .num_children = 1, .child[0] = 4

p[4].index = 4, .num_children = 1, .child[0] = 5

p[5].index = 5, .num_children = 2, .child[0] = 8, .child[1] = 1 p[8].index = 8, .num_children = 1, .child[0] = 7

p[7].index = 7, .num_children = 2, .child[0] = 3, .child[1] = 6 p[3].index = 3, .num_children = 0

p[6].index = 6, .num_children = 1, .child[0] = 2

p[2].index = 2, .num_children = 0

p[1].index = 1, .num_children = 0

5. Let O denote the reversed DFS order.

Using the sample input ﬁle instance10 002.txt, this order O (using the indices of the points) is Suppose point pi is at the head of the order O. There are two possible cases (also refer to lecture slide set lecture11.pdf):

(a) pi has no children (.num children = 0).

.overlap vh to 0, and pi is said processed and removed from O.

(b) pi has .num children > 0 children. In this case, all the children must have been processed. When the edge (.parent, i) is laid as ﬁrst horizontally out of .parent then vertically to reach i, for each combination of how the edges (i, .child[j])’s for j = 0, 1, . . . , .num children −1 are laid, compute the overlap of these .num children +1 edges and add the .overlap xx’s of

all its children. (Here xx corresponds to how the edge (i, .child[j]) is laid out.) This is the total overlap for the combination. Among all combinations, the maximum total overlap is set for the member .overlap hv of point pi.

In the same way, compute .overlap vh for point pi.

Afterwards, pi is said processed and removed from O.

Note: when pi is the root (that is, the last point in O), which has no parent, only the combinations of the child edges are examined to compute .overlap hv for point pi, and we certainly have .overlap vh = .overlap hv.

6. Your program prints to the output the following lines (the last/third set of lines):

The total overlap is .overlap hv (%d) The reduction rate is …(%.2f)

and appends to the instance ﬁle the following comment lines:

#The total overlap is .overlap hv (%d)

#The reduction rate is …(%.2f)

where .overlap hv is replaced by its value for the root, and the reduction rate is calculated as .overlap hv divided by the length of the MST.