## Description

Here in the great State of Ohio, each city is connected to at least one other city

by at least one bi-directional road. In other words, Ohio is laid out as an undirected

graph with some vertices sharing multiple (parallel) edges. Now the State is working

to install recharging stations for electric cars in every city. Your job is to help find the

minimum battery range needed to travel between any two cities in Ohio. Specifically,

what you need to do is first calculate a minimum spanning tree (MST) among

the Ohio cities and then identify within that minimum spanning tree the road with

the longest distance (i.e., the longest edge in the MST). Given this information,

car companies can fine tune their car batteries to ensure that no driver is left stranded

with a dead car battery outside a city.

Implementation and Bonus:

In order to find a minimum spanning tree, you must implement the Prim’s algorithm described on page 728 in the textbook. This is the algorithm described in

Thursday’s lecture, where the details are shown in the attached lecture PPT.

If you recall, this algorithm runs in O(V + V

2 + E) time, where V is the number

of vertices in the graph and E is the number of edges. The O(V

2

) component refers

to the time taken to find every unvisited, minimum weight vertex at the start of the

while loop. The O(E) component results from comparing and possibly updating the

weights of all nodes adjacent to the minimum weight vertices selected at the start

of the while loop. In other words, the for loop within the while loop runs O(E)

operations in total.

If your graph is not too dense (meaning the graph does not contain an overwhelming number of edges), you may want to consider storing the set of unvisited vertices

in a min heap. This will help you find all the mininum weight vertices at the start

of the while loop in O(V log(V )) time as opposed to O(V

2

) time. Of course, when

you now update the weight of a neighboring vertex in the for loop below, you must

also update that vertex’s position in the min heap. As you already know, bubbling

up an element in a min heap of n elements takes just O(log(n)) time, but the initial

searching takes O(n) time. In order to avoid the O(n) search, you must implement

a lookup table that returns a vertex’s index in the min heap in O(1) time. If implemented correctly, the overall time complexity of updating the weight values of

vertices throughout the entire run of the min heap Prim’s algorithm is O(Elog(V )).

In other words, using a lookup table and a min heap, the for loop within the while

loop runs O(Elog(V )) operations in total as opposed the O(E) time in the Prim’s

algorithm described in the previous paragraph. Thus, the total time complexity of

this modified Prim’s algorithm is O(V log(V ) + Elog(V )). As said early, it is more

advantageous to use the min heap version if your graph is not overwhelmingly dense.

In this project, the 6 final grade points will be awarded if you successfully implement the Prim’s algorithm described on page 728 in your textbook. If you successfully

implement the min heap version, you will be awarded the 6 final grade points plus 3

bonus points.

Please note that the Prim2(G, W, n, s) function on page 728 has several

typos. The corrected version can be found in the lecture notes attached

in this assignment.

Input Format:

The input may seem a little strange, so let me explain carefully. The first line of

each input file is the number of test cases T. Each test case is a new graph and thus a

new problem. The first line of each test case is the number of cities N and number of

roads M. The cities are conveniently labeled with integers ranging from 0 to N − 1.

Following the city and road counts are M lines describing the M roads. Each road is

defined as a pair of cities along with the distance between those cities. Remember,

two cities can be connected by more than one road and each road is bi-directional

(undirected). Here is an example:

2

3 2

0 1 5

1 2 7

3 4

0 1 100

1 2 110

1 2 104

2 1 120

The first line indicates the number of test cases T, which in this example is 2. In

the first test case N = 3 and M = 2. So there exists 3 cities and 2 undirected roads

in this graph. Following are the 2 lines describing the roads. The first road connects

city 0 and city 1 and has a length of 5. The second road connects city 1 and city 2

and has a length of 7. After printing out the minimum spanning tree and battery

range for this graph, you will move on to the second test case which has N = 3 cities

and M = 4 roads. Following are the 4 lines describing the 4 roads. Notice that three

roads connect cities 1 and 2. Two of these roads are listed as (1, 2), the other is listed

as (2, 1). Do not be confused by this. You are working with an undirected graph, so

(1, 2) is the same as listing (2, 1).

I will always test with graphs that have a minimum spanning tree. So you should

always make sure every city in your own test files have at least one road connecting

it to another city.

Output Format:

For each test case, print the longest road of the minimum spanning tree on one

line followed by the minimum spanning tree itself. The output for the example given

above is as follows:

7

(1,0,5) (2,1,7)

104

(0,1,100) (1,2,104)

In the first test case, the longest road in the minimum spanning tree is 7, which

lies between cities 1 and 2. So the minimum battery range will be calculated based

on distance 7. Following is the minimum spanning tree which contains only two

roads. These roads lie between cities 1 and 0 with weight 5 and cities 2 and 1 with

weight 7. 104 is the longest road in the second test case. The 2 roads are listed last.

Remember, you should only have N − 1 roads in your minimum spanning trees. DO

NOT worry if the cities in your edges are ordered differently. ‘(0,1,100)’ is the

same thing as ‘(1,0,100)’. Also, DO NOT worry if you end up with a different

minimum spanning tree. Just make sure that it is in fact a minimum spanning tree

though. They all share the same edge weight total.

Turn In:

Submissions will be made through blackboard. If you have multiple files, package

them into a compressed tar file (.tar.gz) or zip file.

Grading:

Total: 100 pts.

• 10/100 – Code style, commenting, general readability.

• 05/100 – Compiles successfully.

• 05/100 – Follows provided input and output format.

• 80/100 – Successfully found the max road length and minimum spanning tree.