如何获得NetworkX图的巨大组件？

Question

我不知道NetworkX最近是否将其中一个方法调整为生成器而不是返回列表,但我正在寻找一种好的(更好的)方法来获取图形的GC.

我有一个工作但非常低效的片段:

# G = nx.Graph()
giant = sorted(nx.connected_component_subgraphs(G), key=len, reverse=True)[0]

有更干净的方式吗？

Answer 1

在 networkx 2.4 中，nx.connected_component_subgraphs()已弃用，因此以下内容应该有效：

Gcc = sorted(nx.connected_components(G), key=len, reverse=True)
G0 = G.subgraph(Gcc[0])

G0 是巨型组件。

谢谢，这是互联网上我发现您需要“子图”方法才能提取最大组件的唯一地方。请注意，在这种情况下 `G.subgraph(max(nx.connected_components(G), key=len))` 会更快。 (3认同)
@IanS 感谢您提供解决方案。文档没有提到返回的组件只是一组节点，而不是子图https://networkx.org/documentation/stable/reference/algorithms/ generated/networkx.algorithms.components.connected_components.html#networkx。算法.组件.connected_components (2认同)

Answer 2

在networkx 1.9中,connected_components_subgraphs返回一个迭代器(而不是一个排序列表).迭代器产生的值不按排序顺序排列.所以要找到最大的,使用max:

giant = max(nx.connected_component_subgraphs(G), key=len)

排序为O(n log n).取最大值是O(n).