# Generating a random minimum spanning tree

I am tring to find the simplest method of generating a random minimum spanning tree.

My intention is to randomly generate a Level in a game where there are n amount of fixed sized rooms existing on a grid which all connect together in a random way.

One method I have come across is to generate random points on a grid and run a Randomized incremental Delaunay triangulation algorithm (Explained quite nicely here) on it with the weights of the nodes being determined by their distances from eachother. Couple this with Kruskal's algorithm and then I will have my minimum spanning tree.

I'm relatively new to this field of Maths and was having trouble creating the Delaunay algorithm (and even more trouble understanding some libraries out there) and thought perhaps there is a simpler method to get the same result.

One method that came to mind was to create a fully connected graph of random points (much simpler for me to do) and then run Kruskal's algorithm on that, However my intuition tells me that this would not be so efficient even though I am only talking about a maximum of 10 or 15 nodes for my intended use.

Are there any other methods I should consider to generate such a graph? I've come across the Prüfer sequence which seems incredibley simple, however with my current understanding of it I do not see how I can take into account the positions of the Rooms/Nodes on the grid or perhaps even chose where to place the nodes on the grid.

• Questions related to a specific programming language are off-topic here. – Yuval Filmus Dec 30 '18 at 20:25
• As Yuval mentioned, you might as well remove the reference to C++ as that raises a red flag to all experienced users here. Your question at this stage is, in fact, largely independent of the programming language. – Apass.Jack Dec 30 '18 at 20:30
• Can you clarify that "$n$ amount of fixed sized rooms" are on the same plane? That is, are we talking about planar graph and Euclidean distance or Manhattan distance or some similar metric distance? – Apass.Jack Dec 30 '18 at 20:33
• @Apass.Jack Ah my bad, I thought if someone knew of a relevant library I could dissect that it would be relevant – Isabella Dec 30 '18 at 20:34
• @Apass.Jack The nodes will be on a grid, but I intended for the weights of the graphs to just be their Euclidean distances, after all the connections will just be there to say what to connect later with corridors etc in a grid space – Isabella Dec 30 '18 at 20:40

1. Generate random points $$p_i$$, $$0\le i\le9$$ in the grid, in whichever way you prefer.