How to create a random graph that is connected?

31 visualizzazioni (ultimi 30 giorni)
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?

Risposte (1)

Christine Tobler
Christine Tobler il 28 Mar 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.

Categorie

Scopri di più su Graph and Network Algorithms in Help Center e File Exchange

Community Treasure Hunt

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

Start Hunting!

Translated by