Space efficient minimum spanning tree

Question

I've come across a task that basically asks you to find MST of the given graph in which all the vertices are connected. I tried using Kruskal's algorithm but I soon figured out that the space bound is too tight for one to store all the edges by a mebibyte, so I also gave up on Prim's and Boruvka's algorithm. Is there a way to implement any of these algorithms (or any other MST algorithm) with space complexity better than O(E) which is in this case O(V^2)?

Answer 1

For the case where you can compute the weights using a function w(i,j) you can compute a minimum spanning tree in space O(n) instead of O(n^2) using Prim's algorithm (https://en.wikipedia.org/wiki/Minimum_spanning_tree#Classic_algorithms).

At each stage maintain the set T of nodes in the tree, and for each node not in the tree maintain the least distance from that node to any node in the tree.

At the start T is node 0 and for each other node you compute the least distance from node 0 to that node.

At each stage pick the node not in the tree with least distance. Now compute the distance from that node to all other nodes not in the tree. If that is less than their current least distance update that least distance.

Storage cost is O(n) to maintain T and O(n) to maintain for each node not in the tree a note of the least distance from the tree to that node.