在NetworkX中完全连接一个未连接的图

Question

我有一个非完全连接的图，我需要通过在图的组件之间随机分配边来将其转换为完全连接的图。是否有一种聪明的方法可以在 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个组件。
如何随机分配最少量的边，以使该图形成完全连接状态？

- Ohm

Answer 1

在这个答案中提到的思路，我们可以遍历连接组件的combinations，并连接两个随机节点。采用combinations的优点在于我们只需要一次遍历组件，并确保在每次迭代时忽略之前看到的组件，因为在combinations中，顺序不重要，也就是说如果我们看到了组合(1,2)，那么我们就不会再看到(2,1)，这可能会导致通过两个不同的节点连接两个组件，从而使它们与图的其余部分隔离开来。

因此，使用您示例的简化版本：

G = nx.fast_gnp_random_graph(100,0.02,seed=1)

plt.figure(figsize=(12,6))
nx.draw(G, node_size=100, node_color='lightgreen')

import random
from itertools import combinations, groupby

components = dict(enumerate(nx.connected_components(G)))
components_combs = combinations(components.keys(), r=2)

for _, node_edges in groupby(components_combs, key=lambda x: x[0]):
    node_edges = list(node_edges)
    random_comps = random.choice(node_edges)
    source = random.choice(list(components[random_comps[0]]))
    target = random.choice(list(components[random_comps[1]]))
    G.add_edge(source, target)

plt.figure(figsize=(12,6))
nx.draw(G, node_size=100, node_color='lightgreen')

- yatu

Answer 2

如果您有5031个组件，则必须分配确切的5030条边来连接您的图形。

这相当简单，您可以贪心地完成。 首先，计算组件集C（您可以将组件表示为一组顶点）。 然后按照以下方式执行（伪代码）：

C = connected_components_of(the_graph)  # set of sets of vertices
while len(C) < 2:
    c1 = C.pop()
    c2 = C.pop()
    v1 = choose_random_vertex_in(c1)
    v2 = choose_random_vertex_in(c2)
    add_edge(v1, v2)
    C.add(c1 | c2)

而且这个图将是连通的。

- m.raynal