biconnected_components

biconnected_components(G)

返回一组节点的生成器，每个图的双连接组件一组

双连接组件是最大的子图，这样移除节点（以及该节点上的所有边）不会断开子图。请注意，节点可能是多个双连接组件的一部分。这些节点是关节点或切割顶点。删除关节点将增加图形中连接的组件的数量。

注意，按照惯例，dyad被视为双连接组件。

参数

G网络X图表

无向图。

返回

nodes发电机

节点集合的生成器，每个双连接组件对应一个集合。

加薪

NetworkXNotImplemented

如果输入图不是无向的。

参见

is_biconnected

articulation_points

biconnected_component_edges

k_components

此函数是一种特殊情况，其中k=2

bridge_components

与此函数类似，但定义时使用的是2边缘连接而不是2节点连接。

笔记

查找连接点和双连接组件的算法是使用非递归深度优先搜索（DFS）实现的，该搜索跟踪后边缘在DFS树中达到的最高级别。节点 n 当且仅当存在根于的子树时，是一个连接点。 n 这样就不会有任何后缘来自 n 链接到 n 在DFS树中。通过跟踪DFS所遍历的所有边，我们可以获得双连接组件，因为双组件的所有边将在连接点之间连续遍历。

工具书类

1

Hopcroft，J.；Tarjan，R.（1973）。”图形处理的有效算法”。ACM通信16:372–378。内政部：10.1145/362248.362272

实例

>>> G = nx.lollipop_graph(5, 1)
>>> print(nx.is_biconnected(G))
False
>>> bicomponents = list(nx.biconnected_components(G))
>>> len(bicomponents)
2
>>> G.add_edge(0, 5)
>>> print(nx.is_biconnected(G))
True
>>> bicomponents = list(nx.biconnected_components(G))
>>> len(bicomponents)
1

您可以使用sort生成双连接组件的排序列表，首先是最大的。

>>> G.remove_edge(0, 5)
>>> [len(c) for c in sorted(nx.biconnected_components(G), key=len, reverse=True)]
[5, 2]

如果只需要最大的连接组件，那么使用max而不是sort会更有效。

>>> Gc = max(nx.biconnected_components(G), key=len)

要将组件创建为子图，请使用： (G.subgraph(c).copy() for c in biconnected_components(G))