The Missouri Park and Recreation Association would like to build a recreation trail for biking and hiking that connects the cities of Jefferson City, Kansas City, Springfield, St. Joseph, and St. Louis. The distances in miles between these cities are given in the table.

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

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

Transcribed Image Text:

Jefferson Kansas St. City City Springfield Joseph St. Louis Jefferson 158 138 215 134 City Kansas 158 191 56 249 City Springfield 218 138 191 227 St. Joseph 307 215 56 227 St. Louis 134 249 218 307