Description
EE3980 Algorithms Given a weighted undirected connected graph G(V, E), it is known that greedy algorithms can be applied to find the minimum-cost spanning tree. In this homework, your assignment is to write an efficient C program to solve the minimum-cost spanning tree problems. Nine such graphs are given in g3.dat, g4.dat, · · · , g11.dat files. The first line of each file contains the number of vertices and edges in the graph, |V | and |E|. The vertices of the graph are always named from 1 to |V |. The files are then followed by the edges of the graph. Each edge is described by two vertices followed by the weight of the edge. The content of g3.dat is listed at the end of this PDF file as an example. The output of your program should have the following format: Minimum-cost spanning tree: 1: <1 2> 0.01 2: <1 4> 0.02 3: <1 5> 0.03 4: <2 3> 0.04 5: <2 6> 0.07 6: <4 7> 0.11 7: <4 8> 0.12 8: <5 9> 0.16 |V| = 9 |E| = 20 Minimum cost: 0.56 CPU time: 1.90735e-06 seconds As usual, you should measure the CPU time in finding the spanning tree, and correlate it to the theoretical time complexity of your algorithm. The space complexity should also be analyzed and discussed in your report. Notes. 1. One executable and error-free C source file should be turned in. This source file should be named as hw08.c. 2. A report file in pdf format is also needed. This file should be named as hw08a.pdf. 3. Submit your hw08.c and hw08a.pdf on EE workstations using the following command: ∼ee3980/bin/submit hw08 hw08.c hw08a.pdf 1 where hw08 indicates homework 8. 4. Your report should be clearly written such that I can understand it. The writing, including English grammar, is part of the grading criteria. The contents of g3.dat file is shown below. 9 20 5 6 0.13 2 4 0.05 8 9 0.20 1 4 0.02 2 6 0.07 6 9 0.18 6 8 0.17 2 5 0.06 2 3 0.04 5 8 0.15 5 9 0.16 3 6 0.09 4 8 0.12 4 7 0.11 1 2 0.01 1 5 0.03 5 7 0.14 4 5 0.10 3 5 0.08 7 8 0.19 This graph has 9 vertices and 20 edges. The first edge connects vertices 5 and 6 and has the weight of 0.13. The rest of the 19 edges followed on each line. 2
