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

2024-05-08 • 问答

我是编程新手，我正在尝试解决一个问题，即“找到一个空的无向图需要连接的平均边数” ....它还要求“保持对孤立组件的跟踪”一路走来。。。

我可以添加节点：

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 然后我尝试选择两个随机节点，并将它们与这样的边连接：

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

但是它不起作用...知道吗？

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

作为示例，以下代码生成具有N个顶点的图形，并迭代地添加随机边（无重复）。连接结果图后，该过程停止，并返回使其连接所需的边数。

 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中连接起来？

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

大家都在问