How to create a random graph that is connected?
27 visualizaciones (últimos 30 días)
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?
Christine Tobler el 28 de Mzo. de 2023
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.