How to create a random graph that is connected?

3 次查看（过去 30 天）
Tirthankar Chakraborty
回答： Christine Tobler 2023-3-28
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?

请先登录，再回答此问题。

回答（1 个）

Christine Tobler
Christine Tobler 2023-3-28
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.

类别

在 Help Center 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by