How to create a random graph that is connected?

I am using the following code for generating a random graph with 'n' nodes and 'E' edges.

n = 50;
E = 100;
 
adj = spalloc(n, n, E);
idx = randperm(n * n, E);
adj(idx) = 1;
adj = min( adj + adj.', 1);

G = graph(adj,'omitselfloops');

The problem is that sometimes I end up with disconnected nodes or a graph with more than one connected component.

How can I make sure that my random graph (without repeated edges and self loops) is connected?

Answer 1

[Christine Tobler]

If an undirected graph is connected, it must contain at least one path that visits each node at least once.

You could construct an initial matrix where the second off-diagonal (adj(1, 2), adj(2, 3), ..., adj(n-1, n)) is always nonzero, and fill in the rest of the matrix randomly with E-n other edges. After that, you would choose a random permutation of the nodes (ind = randperm(n); adj = adj(ind, ind);), which should reach any possible random and completely connected graph with the same probability.