我有一个非完全连通的图,我需要通过在图的组件之间随机分配边将其转换为完全连通的图。在networkx
中有没有一种聪明的方法
例如,如果我有以下图表:
>>> import networkx as nx
>>> G = nx.fast_gnp_random_graph(10000,0.0001,seed=1)
>>> print("Connected?",nx.is_connected(G))
Connected? False
它有5031个组件。
如何随机分配使此图完全连接所需的最小边数
Tags:
按照this answer中的思想,我们可以迭代连接组件的^{} 并连接随机的节点对。使用
combinations
的优点是,我们只需要在组件上迭代一次,并且我们确保在每次迭代中忽略以前看到的组件,因为combinations
顺序并不重要,也就是说,如果我们看到了组合(1,2)
,我们就不会看到(2,1)
,这可能导致两个组件通过两个不同的节点连接,并且可能与图的其余部分隔离因此,使用示例的简化版本:
如果有5031个组件,则必须精确指定5030条边才能连接图形
这很简单,你可以贪婪地做这件事。
首先,计算组件集
C
(您可以将组件表示为一组顶点)。然后执行以下操作(伪代码):
图表将是connex
相关问题 更多 >
编程相关推荐