Thought Process

In Mathematics this is called finding the Minimum Spanning Tree (MST) of a graph. It's very easy to do by hand, but it was a fun challenge to make an algorithm. I decided to replicate Prim's Algorithm because that was a 15 mark question on my final exam and I crushed it.

Before I start the algorithm I first sum all the values in the top right triangle, to get the old sum. Then we continue with the steps, verbatim from Wikipedia:

1. Initialise a tree with a single vertex, chosen arbitrarily from the graph.

2. Grow the tree by one edge: of the edges that connect the tree to vertices not yet in the tree, find the minimum-weight edge, and transfer it to the tree.

3. Repeat step 2 (until all vertices are in the tree).

My code is including below!