biconnected_components

biconnected_components(G)

返回一个节点集合的生成器，每个集合对应图中的一个双连通分量

双连通分量是最大子图，移除一个节点（及其所有关联边）不会断开子图。注意，节点可能属于多个双连通分量。这些节点是关节点，或割点。移除关节点会增加图的连通分量数量。

注意，按照惯例，一个二元组被视为一个双连通分量。

Parameters:

GNetworkX 图

一个无向图。

Returns:

nodes生成器

节点集合的生成器，每个集合对应一个双连通分量。

Raises:

NetworkXNotImplemented

如果输入图不是无向图。

See also

is_biconnected

articulation_points

biconnected_component_edges

k_components

此函数是 k=2 的特例

bridge_components

类似于此函数，但定义使用 2-边-连通性而非 2-节点-连通性。

Notes

查找关节点和双连通分量的算法实现使用了一个非递归的深度优先搜索（DFS），该搜索跟踪回边在DFS树中达到的最高级别。节点 n 是关节点当且仅当存在一个以 n 为根的子树，该子树中没有任何后继节点通过回边连接到 n 的前驱节点。通过跟踪DFS遍历的所有边，我们可以获得双连通分量，因为双连通分量的所有边在关节点之间连续遍历。

References

[1]

Hopcroft, J.; Tarjan, R. (1973). “Efficient algorithms for graph manipulation”. Communications of the ACM 16: 372–378. doi:10.1145/362248.362272

Examples

>>> 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

你可以生成一个按大小排序的双连通分量列表，从大到小。

>>> 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))