如何将随机边添加到空图，直到它在 python 中连接起来？

Question

我是编程新手，我正在尝试解决一个问题 "find the average number of edges that an empty undirected graph needs to become connected"...它还要求 "keep track of isolated components along the way"...

我可以添加节点:

from random import random, choice

import networkx as nx

G = nx.Graph()
i = int(input("enter the number of desired nodes : "))
for node in range(0, i):
    G.add_node(i)  # creates a graph with desired number of nodes
    i = i - 1

输出类似于 10 9 ... 1 然后我尝试 select 两个随机节点并用这样的边连接它们：

first_node = choice(G.nodes())
second_node = choice(G.nodes())
print(first_node, second_node) # print which nodes are selected

但它不起作用...有什么想法吗？

Answer 1

您需要更具体地说明您要尝试完成哪种模拟，因为图形生成有不同的随机过程。请告诉我更具体的信息，我可以编辑答案。

例如，下面的代码生成一个有 N 个顶点的图，并迭代地添加随机边（不重复）。当生成的图被连接并且 returns 连接所需的边数时，该过程停止。

 from itertools import combinations
 from random import choice
 def simulate(n): 
     G = nx.Graph() 
     G.add_nodes_from(range(n)) 
     E = list(combinations(range(n), 2)) 

     while True: 
         e = choice(E) 
         E.remove(e) 
         G.add_edge(e[0], e[1]) 
         if nx.is_connected(G): 
             return G.size()

从这里我们可以看出，平均而言，我们需要向具有 20 个顶点的图添加 32 条（随机）边，才能使其连通。

In [24]: L = [simulate(20) for _ in range(1000)]                                

In [25]: sum(L)/len(L)                                                          
Out[25]: 32.739

如何将随机边添加到空图，直到它在 python 中连接起来？

how to add random edges to an empty graph untill it becomes connected in python?

python

connected-components