Prim's Minimum Spanning Tree Algorithm

Author: Yonatan David and Tim Heyer

In this assignment, you will apply Prim's algorithm and the concept of a minimum spanning tree to a real-world network optimization problem.

Note: Prim's Algorithm is discussed in detail in Section 23.2 (pg. 634) of the text.

As such, the tree will contain all vertices of its corresponding graph, and must visit each vertex in a specific order. The minimum spanning tree of a graph is one that is:

- connected
- acyclic
- inclusive of all vertices
- the minimum total weighting for its edges

- Network design
- Taxonomy
- Handwriting recognition

- Given a start vertex, compare the weights of all reachable edges and choose the one with the least weight. If there are multiple edges with the same weight, choose one of the edges.
- Visit the vertex to which the edge connects.
- Reevaluate all available edges, including previously visited vertices and their respective edges. Choose the edge with the least weight that leads to an unvisited vertex.
- Repeat step 3 until all vertices have been visited.

As you visit new vertices, be sure to map the new vertex to the edge you took to reach it in thetoEdgemap. This map will be used to calculate the total distance traveled and will become your minimum spanning tree.

Note that telephone service can travel to any city connected to the network you install. As such, every city does not need a wire to every other city; there only needs to be one common wire which connects every city.With the layout of the country in hand, you must now figure out how to connect every city while minimizing your firm's costs and therefore maximizing their profits. You quickly identify that you'll need to construct a minimum spanning tree of the cities and their distances to determine along which paths you'll need to install wire. Luckily, you're familiar with Prim's algorithm so you fire up Eclipse and begin writing a solution in your favorite programming language, Java.

- Update your repository as usual.
- In the
`prim.util`package of the`extensions`source folder, notice that the graphing classes are similar to those used in the Dijkstra's shortest path lab, but are slightly modified to use an undirected graph instead of the previously used directed graph. Familiarizing yourself with these classes will make this assignment much easier. - In the
`prim`package, find and open the`MinimumSpanningTree`class. - Complete the
`run()`method using the steps of Prim's algorithm outlined above. - Pass the unit tests (Note: the test can take up to a minute to finish running).

The unit tests work by constructing a graph with a preconfigured minimum spanning tree. While it is true that in general, graphs will often have more than one MST (though all with the same total weight), the graph generated by the unit tests will have only one. Therefore, by following all of the steps in Prim's algorithm you will find and return the same MST known to the test.

When you done with this extension, you must be cleared by the TA to receive credit.

- Commit all your work to your repository
- Fill in the form below with the relevant information
- Have a TA check your work
- The TA should check your work and then fill in his or her name
- Click
OKwhile the TA watches- If you request propagation, it does not happen immediately, but should be posted in the next day or so

This demo box is for extension 6.1