Length of MST, Adjacency Matrix

Question

So here is the problem:

Ignore problem 7, i blanked out irrelevant parts.

I already know that the answer to Problem 8 is 13 as stated in the picture. But i dont know how to algorithmically come to this conclusion.

I know how to create a MST from a graph using Prims Algorithm, but I feel like there is a better way to quickly come up with an answer here.

Answer 1

As it says in this link :

This problem can be solved by many different algorithms. It is the topic of some very recent research. There are several "best" algorithms, depending on the assumptions you make:

• A randomized algorithm can solve it in linear expected time.¹
• It can be solved in linear worst case time if the weights are small integers.²
• Otherwise, the best solution is very close to linear but not exactly linear. The exact bound is O(m log beta(m,n)) where the beta function has a complicated definition: the smallest i such that log(log(log(...log(n)...))) is less than m/n, where the logs are nested i times.³

These algorithms are all quite complicated, and probably not that great in practice unless you're looking at really huge graphs. The book tries to keep things simpler, so it only describes one algorithm but doesn't do a very good job of it. I'll go through three simple classical algorithms (spending not so much time on each one).

So it is better to stick with Prim or Kruskal

1. Karger, Klein, and Tarjan, "A randomized linear-time algorithm to find minimum spanning trees", J. ACM, vol. 42, 1995, pp. 321-328.
2. Fredman and Willard, "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", 31st IEEE Symp. Foundations of Comp. Sci., 1990, pp. 719--725.
3. Gabow, Galil, Spencer, and Tarjan, Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, vol. 6, 1986, pp. 109--122.