Challenge 06: Minimum Spanning Trees

Problem overview

Given an undirected graph, determine the minimum spanning tree. For instance, in the example graph below, the minimum spanning tree would have a total edge weight of 10 and consists of the following edges:

(A, C)
(B, C)
(C, E)
(D, E)
(D, F)

Inspiration

This problem is inspired by Challenge #152 [Hard] Minimum Spanning Tree from the DailyProgrammer subreddit.

Input / Output

You will be given a series of graphs specified by a distance matrix as shown below. You are to compute the minimum spanning tree and output the total edge weight of the tree and the edges in the tree.

NVERTICES
-1 -1 ...
-1 -1 ...

The first line specifies the number of vertices in the undirected graph, which will be between 1 and 26 (inclusive). This is followed by a distance matrix with each row separated by newlines and each column separated by spaces:

1. -1 is used to denote there is no edge between a pair of vertices.
2. The vertices are assumed to be named A, B, C, D and so on, with the matrix representing them in that order (left-to-right and top-to-bottom).

Example

Given this following input:

6
-1  4  2 -1 -1 -1
 4 -1  1  8 -1 -1
 2  1 -1 -1  4 -1
-1  8 -1 -1  2  1
-1 -1  4  2 -1  7
-1 -1 -1  1  7 -1
5
-1  2  6 -1 -1
 2 -1  4  1 -1
 6  4 -1 -1  1
-1  1 -1 -1  1
-1 -1  1  1 -1

Your program should output the following:

10
AC
BC
CE
DE
DF

5
AB
BD
CE
DE

Note that a blank line between MSTs will be required to pass the tests used for grading

Requirements

You must implement Prim's Algorithm to compute the minimum spanning tree.

---

Rubric

We will grade your submission relative to the rubric below.

+2    Code is well formatted, commented (inc. name, assignment, and overview), with reasonable variable names
+5    Uses Prim's algorithm as required
+28   Test cases successfully solved (4 points each)

Testing your code prior to submission

To faciliate testing, you were previously asked to clone the course Github repository as follows:

git clone https://github.com/semrich/ds302_20.git cs302

For this assignment, update this clone by using the following:

git pull

We'll discuss this in class but note that your program must be named "solution.cpp" and compilable using make. To test your solution against ours, type:

make test

---

Submission

To submit your solution, you must submit a single archive (.zip, .tar, .gz, etc.) on Canvas prior to the deadline.

Note: Although submission will be faciliated by Canvas, we will compile and test on EECS lab machines!

If you develop your solution elsewhere please make sure it works on the lab computers prior to the deadline

---