Given an undirected graph, determine the minimum spanning tree.
For instance, in Graph 0 above, the minimum spanning tree would
have a total edge weight of 10
and consist of the following edges:
(A, C) (B, C) (C, E) (D, E) (D, F)
You will be given a series of graphs specified by a distance matrix. You are to compute the minimum spanning tree and output the total edge weight of the tree and the edges in the tree.
Note, this problem is inspired by Challenge #152 [Hard] Minimum Spanning Tree from the DailyProgrammer subreddit.
You will be given a series of undirected graphs from standard input in the following format:
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
is used to denote there is no edge between a pair of vertices.
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).
For each undirected graph, you are to print out the total weight of the
minimum spanning tree, and then the edges of the minimum spanning tree
represented by the two vertices such as AB
in lexicographical order.
Given the 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: You must put an empty line between the outputs of each graph.
You should represent the graph using an adjacency matrix.
You should perform Prim's Algorithm to compute the minimum spanning tree.
To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Challenge 10 - TA assignment list.
To facility the Merge Request workflow, you must do your development in its own branch:
$ cd path/to/repo # Go to your repository $ git checkout master # Make sure we are on master branch $ git pull # Make sure we have changes for GitLab $ git pull upstream master # Fetch and merge upstream changes $ git checkout -b challenge10 # Create challenge10 branch ... # Do your work $ git commit # Commit your work (can do this multiple times) $ git push -u origin challenge10 # Push branch to GitLab
For one extra credit point, you can try out the Challenge 10: Extra Credit Challenge.