How to create a random graph that is connected?

27 visualizaciones (últimos 30 días)
Tirthankar Chakraborty
Tirthankar Chakraborty el 28 de Mzo. de 2023
Respondida: Christine Tobler el 28 de Mzo. de 2023
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?

Respuestas (1)

Christine Tobler
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.


Más información sobre Graph and Network Algorithms en Help Center y File Exchange.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by