Description
✔✔✔✔✔
Input
You program should read an input file name from the command line and uses the adjacency matrix read from the input file with a format as follows.
- The integer number of vertices in the graph.
- The positive real number weights of one vertex per line, delimited by a space. The value 0.0 is used as no connection.
A sample input file can be created using the provided program, generateAdjM.cpp. You may use the program directly, or adapt it, to create graphs for your algorithms without modifying the output format. If you adapt the program to generate adjacency matrices of different characteristics, you should add a header to the code to explain what you have modified. Output
MST output
The MST from each algorithm should be saved in a text output file named with prefix, output_mst_*.txt, that contains the edges of MST as a sequence of edges, in selected order using the algorithm * from node 1, each edge and its weight per line and the minimal weight at the last line. Algorithm 1 is always for the brute-force algorithm and algorithm 2 and so on for your other algorithms. For instance,
1-4 2.3
4-3 1.9
4-2 3.2 …
4-2 3.2
45.6
Statistics output
The output should be displayed to standard output. For each algorithm, the output should consist of the following data, clearly labelled: (CSCI203 students only have one output for Prim’s algorithm.)
Number of vertices: **
- Brute-force algorithm 1: *** (time unit)
- Prim’s algorithm 2 (matrix): *** (time unit)
- Prim’s algorithm 3 (heaps): *** (time unit)
You may save this information to a file for your analysis and easy plotting later.
