Due Thursday, Apr 24 at 11:59 P.M.
Please keep in mind the policy on collaboration, as described on the syllabus.
Your code will be graded for style as well as correctness and should conform to the following style guidelines.
Write a program that inputs a graph and outputs its minimum spanning tree using O(n2)-time Prim's algorithm as discussed in class and in the book.
The input format is as follows:
an integer indicating the number n of nodes in the graph, followed by
triples of integers, where each triple indicates the two endpoints
of an edge and its weight. The nodes are numbered from 0 to n-1.
A triple of 0 0 0 indicates the end of the input. For example, the graph
from Section 12.6 of the book is input as
6
0 1 3
0 2 3
0 3 3
0 4 3
0 5 3
1 2 2
1 5 2
2 3 4
2 4 2
3 4 4
4 5 1
0 0 0
You can assume the input is in the correct format.
The outputs format is essentially the same (except the ending 0 0 0, which you
don't need in an output): an integer (by itself on the first line)
indicating the number of nodes
in the tree, followed by space-separated triples of
integers,
one per line, indicating the edges in a tree and their weights.
Each edge must be shown exactly once, go from the lower-numbered node
to a higher-numbered node (e.g., 0 1 3, not 1 0 3), and all
the edges must be ordered by the node of origin. For example,
for the above input graph, the correct output is
6
0 1 3
0 3 3
1 2 2
2 4 2
4 5 1
Not Connected!
Please follow the input and output formats exactly, or we will deduct significant amounts of points for making the grader's life difficult. We will use input/output redirection (Unix command-line options < and >) for grading, and recommend you use the same for testing -- it will make your lives easier.
You may use any representation of the graph you want, although
it's probably easiest to use the array-based. You may also find
the following definition of infinity useful. If you have a class
Graph, put the following line in the definition of the class:
const static int infinity;
and the following line into graph.cpp:
const int Graph::infinity = numeric_limits<int>::max();
Be sure to #include the file limits for
this to work. Using this is not mandantory -- use it
only if it helps you. Note that this infinity is guaranteed to be greater
than any other integer.
Submit all the files needed to compile your program, including
Makefile. The grader should be able to compile your code
simply by typing make. If he can't, we'll take off points.
Put everything into directory hw6.