现有的Python库具有接受numVertices和numEdges的功能，然后总是生成连接图吗？

Question

• 我想生成一个包含n个顶点和m个边的连接的无向图。特别是，我想生成一个图，其节点正好包含从0到n - 1的每个整数之一。

• 我尝试使用NetworkX库的random_internet_as_graph函数，但是我意识到它仅接受自定义数量的顶点。实际上，它只会自行决定生成多少个边。

• 我在此站点上已进行了深入研究，找不到我想要的东西。我将不胜感激。谢谢！

Answer 1

我不了解现有库，但这是从头开始的解决方案。假设您有n个节点和m个边。要生成简单（无重复边）的连通图，m，n必须满足以下条件：

n - 1 <= m <= n * (n - 1) / 2

进程（节点从0到n-1的索引）：

1. 生成生成树以确保图形已连接。有很多方法（例如，Prufer序列），但这是一个简单的方法：

for i = 1 to n - 1:
     add_edge(i, randint(0, i - 1))

为了使它看起来更加随机，您可以先将节点的顺序重新排列。

2. 添加更多的边缘，直到有m个边缘。

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]的随机整数。

这些代码看起来很简单，但实际上工作非常快。您可以计算预期的迭代次数以了解原因。