CPSC 212
(Data Structures and Algorithms)
Assignment 7

Objectives:

Implement Prim's MST algorithm.

Due date:

10/31/06

What to hand in:

Code "tarball" (e.g., asg7.tar.gz) including:

1. README file containing assignment and solution descriptions, e.g., program design, description of algorithm, etc., if appropriate.
2. INSTALL file containing any specific compliation quirks peculiar to your program, e.g.,
   Compilation: make -f Makefile.smirp.
3. USAGE file containing any specific usage quirks peculiar to your program, e.g.,
   Usage: ./smirp < smirp.in where ./smirp is the executable and smirp.in is the input.
4. src/ directory with source code.

Description:

1. Implement Prim's MST algorithm in 2D:
   1. Read in a list of n 2D points (or 3D points each with its z-coordinate set to 0.0), e.g.,

      vector<Point* > pts;
Point* ptp;
while(std::cin >> (ptp = new Point(0.0,0.0)))
   pts.push_back(ptp);

   2. Resize your graph so that it can hold n nodes, e.g.,

      graph.resize((int)pts.size());

   3. Add all verteces to the graph, making sure that for each vertex sufficient memory is allocated to hold n-1 adjacent neighbors (for a complete graph), e.g.,

      for(int i=0; i<(int)pts.size(); ++i)
  graph.addVertex(i,pts[i],(int)pts.size()-1);

   4. Construct a complete graph, e.g.,

      for(int i=0; i<(int)pts.size(); ++i)
  for(int j=0; j<(int)pts.size(); ++j)
    if(i!=j) graph.addEdge(i,j);

   5. Execute Prim's algorithm using the first node as the MST root, e.g.,

      graph.prims(0);

   6. Retrieve MST edges from graph (there should be twice as many points as there are MST edges), e.g.,

      vector<Point* > mst_pts;
graph.edges(&mst_pts);

   7. Print out the edges, e.g.,

      for(int j=0; j<(int)mst_pts.size(); ++j)
    std::cout << mst_pts[j];

2. Sample input and output can be found here: smirp.in, smirp.out.