The Darlington County, South Carolina, tourism office wishes to build a horse trail that connects the towns of Darlington, Hartsville, Lamar, and Society Hill. The distances, in miles, between these cities are given in the table below.

(a) Use Kruskal’s algorithm to determine the minimum-cost spanning tree that would link each city to create the least expensive horse trail. 

(b) If the cost of building such a trail is $3500 per mile, what would be the cost of building the trail determined in part (a)?

Transcribed Image Text:

Society Hill Darlington Hartsville Lamar Darlington 12 14 15 Hartsville 12 13 16 Lamar 14 13 26 Society Hill 15 16 26