我想生成一个包含n个顶点和m个边的连接的无向图。特别是,我想生成一个图,其节点正好包含从0
到n - 1
的每个整数之一。
我在此站点上已进行了深入研究,找不到我想要的东西。我将不胜感激。谢谢!
我不了解现有库,但这是从头开始的解决方案。假设您有n个节点和m个边。要生成简单(无重复边)的连通图,m,n必须满足以下条件:
n - 1 <= m <= n * (n - 1) / 2
进程(节点从0到n-1的索引):
for i = 1 to n - 1:
add_edge(i, randint(0, i - 1))
为了使它看起来更加随机,您可以先将节点的顺序重新排列。
while there are less than m edges:
a, b = randint(0, n - 1), randint(0, n - 1)
if (a != b and edge(a, b) has not existed):
add_edge(a, b)
注意:randint(a, b)
=范围为[a,b]的随机整数。
这些代码看起来很简单,但实际上工作非常快。您可以计算预期的迭代次数以了解原因。