How to Generate Random Connected Graphs

Revision en1, by upobir, 2020-05-26 16:23:39

As the title says, I wanna generate random graphs that are connected. Now there are some details herr, obviously I want the graph to have $$$n$$$ nodes which is predetermined. Something else that arises in competitive programming is that the graph should have $$$m$$$ edges(also predetermined). Now how does one do that in an intelligent way.

Now I have done a little bit of googling, and ut seems there are no 'Good' way of getting a perfectly 'random' such graph i.e. pick one uniformly from all graphs with n nodes and m edges. But that's okay an approximately random is also good.

One way I have considered is make a spanning tree first then add extra edges. But this has horrible bias for certain graphs. For example for $$$n$$$ node $$$n$$$ edge graph, a cycle graph $$$(1-2-3-...-n-1)$$$ is $$$\frac{n}{3}$$$ times more likely than path $$$(1-2-3-4-...-n)$$$ + edge $$$(1-3)$$$. So what process can be a good choice?

Tags #graph, generated test, random


  Rev. Lang. By When Δ Comment
en2 English upobir 2020-05-26 16:52:20 22
en1 English upobir 2020-05-26 16:23:39 936 Initial revision (published)