Homework 8. Minimum-Cost Spanning Tree

EE3980 Algorithms
Homework 8. Minimum-Cost Spanning Tree

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