CS 223 In-lab 9
Week of 4/3

For CS 223, in-labs will consist of a mix of exercises and problems and short programming assignments.  These will be due at the end of the lab period.  You may occasionally be assigned homework problems as well.  Homework will always be due at the beginning of the next lab.

Minimum Spanning Trees

For this in-lab, your goal is to write a program to compute a minimum spanning tree using Prim's algorithm (see the CLRS textbook for the algorithm).  Prim's algorithm is pretty simple but requires a priority queue data structure.  You may either use Java's built-in PriorityQueue class, or you can use your own that you implemented for Out-lab 1. 

Input: Your program should read an undirected weight graph from a file.  The file format is:

<number of vertices>
<number of edges>
<endpoint 1> <endpoint 2> <weight> (edge 0)
<endpoint 1> <endpoint 2> <weight> (edge 1)
...

Example:
4
4
0 1 5
1 2 10
2 3 15
3 0 20
represents the following graph:

  v0  5   v1
   +------+
   |      |
20 |      | 10
   |      |
   +------+
  v3  15  v2

As you can see in the example, we assume that vertices begin with index 0.  You should also use vertex 0 as the root.

Output: Print out which edges belong to the MST for the input graph.  Example:

MST for input graph:
(v0, v1), (v1, v2), (v2, v3)
Total weight: 30

Hints:

  • You should create a class called Vertex that implements the PriorityQueue interface.  Vertices also need to contain the following data:
    • the index of the vertex
    • a list of the adjacent vertices
    • a parent vertex (this is the pi value in the pseudocode)
    • a key value (integer)
       
  • When you read in the number of vertices, just create this many Vertex objects and store them in an array.
     
  • The easiest way to store the edge weights is with a matrix.  You should create a symmetric 2d array that stores the weight between each pair of vertices that are connected with an edge (just populate this array as you read in the edges from the input file).
     
  • To keep track of the edges in the MST, each time EXTRACT-MIN is called and returns a vertex u > 0 (i.e. not the root), then just add the edge (u, parent(u)) to the list of MST edges.  You could just immediately print the edge, rather than storing it.  At the end, this list will consist of the entire MST.
     

What to Turn In

  • Source code and two sample runs (the above and a graph of your own creation with at least 10 edges).
  • If you don't finish in time, you may turn in your code the following day (email or drop in Will's mailbox next to the main CS office).