Minimum Spanning Tree on US Cities - 44

Example Image

Goals

The purpose of this assignment is to learn to

1. Implement Prim's Minimum Spanning Tree Algorithm and demonstrate its application using US city data.
2. Use the BRIDGES Graph class to store the input graph
3. Experiment with two variants of the algorithm
4. Visualize the results using BRIDGES

Description

Tasks

1. Build the graph using the US City data - refer to the tutorial in help for accessing the data

2. Implement Prim's MST algorithm, using the US City data

   • Variant 1: Greedy operation uses the entire unvisited graph
   • Variant 2: Greedy operation visits only the fringe nodes of the tree

3. Visualize using BRIDGES

   • Highlight the starting city
   • Label the nodes with city names
   • Use the map facilities in BRIDGDES to embed the MST in a US map, using the setMapOverlay() and setMap() methods of the BRIDGES class.

Extensions

Greedy Search operation uses the entire unvisited graph 
Greedy Search operation visits only the fringe nodes of the tree

Help

US cities

Java

GraphAdjList

C++

GraphAdjList

Python

GraphAdjList Python