Several communities in eastern Pennsylvania wish to establish a commuter rail train system between the cities shown in the map below (distances are in miles).

a) Use Kruskal’s algorithm to determine the minimum-cost spanning tree that would link the cities using the shortest distance.

b) If it costs $1,300,000 per mile of railroad track, how much does the commuter rail system determined in part (a) cost?

Transcribed Image Text:

Allentown 82 44 57 59 Harrisburg Reading 60 37 33, 25 72 25 Lancaster 96 York Philadelphia