Mike is tired of snooping on hardworking Americans who pay his salary^{1}. Despite the generous benefits, working for the federal government... is not that great. Unlimited and unchecked access to everyone's data sounds fun, but he'd rather be properly compensated for his service. Instead, Mike wants to sell out and join Seb on the fruit farm^{2} where they totally believe in privacy. Totally.
While attending WWDC23 and witnessing the unveiling of the Vision
Pro^{3}, Mike met a Notre Dame Computer Science and Engineering alumna
who suggested that maybe he should consider joining the cult^H^H^H^H
company^{4}. After some consideration (very brief), Mike decides he
wants to give it a shot. As a long time fruit farm consumer and
advocate, he would feel at home at the company, and would get a strong
sense of belonging and fulfillment, which is really what he is currently
missing in his current position.
Inspired and fueled by the magic of the fruit farm, Mike decides to buckle down and grind some programming challenges (without GPT and Co-Pilot!) in order to ace his future technical interviews. In searching for some more exotic and off-beat programming problems, he comes across the DailyProgrammer subreddit which posts different programming puzzles for users to try out and share.
After some surveying, he comes across a challenging problem about minimum spanning trees:
Given an undirected graph in the form of an adjaceny matrix, determine the weight of the minimum spanning tree and its associated edges.
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.
Unfortunately, his data structures knowledge is a bit rusty and this is a bit of a struggle for him... likewise, the ongoing Reddit Blackout is making it difficult for him to access information on Reddit, so he decides to ask for your help once again on coming up a solution for the problem described above.
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 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).
Here is an example of the input for the problem (corresponding to Graph 0 and Graph 1 in the diagram above):
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
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.
For example, given the input above, you 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.
For each input test case, your solution should have the following targets:
Time Complexity | O(VlogV) , where V is the number of vertices in the graph. |
Space Complexity | O(V+E) , where V is the number of vertices and E is the number of edges in the graph. |
Your solution may be below the targets, but it should not exceed them.
To submit your work, follow the same procedure you used for Reading 01:
$ cd path/to/cse-30872-su24-assignments # Go to assignments repository
$ git checkout master # Make sure we are on master
$ git pull --rebase # Pull any changes from GitHub
$ git checkout -b challenge18 # Create and checkout challenge18 branch
$ $EDITOR challenge18/program.py # Edit your code
$ git add challenge18/program.py # Stage your changes
$ git commit -m "challenge18: done" # Commit your changes
$ git push -u origin challenge18 # Send changes to GitHub
To check your code, you can use the .scripts/check.py
script or curl:
$ .scripts/check.py
Checking challenge18 program.py ...
Result Success
Time 0.03
Score 6.00 / 6.00
$ curl -F source=@challenge18/program.py https://dredd.h4x0r.space/code/cse-30872-su24/challenge18
{"result": "Success", "score": 6, "time": 0.03165841102600098, "value": 6, "status": 0}
Once you have committed your work and pushed it to GitHub, remember to create a pull request and assign it to the instructor.