biconnected_components#

biconnected_components(G)[source]#

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

双连通分量是极大子图，移除其中的任何一个节点（及与该节点相关联的所有边）都不会使子图断开。请注意，节点可能属于多个双连通分量。这些节点称为关节点或割点。移除关节点会增加图的连通分量数量。

注意，按照惯例，一个二节点图（dyad）被视为一个双连通分量。

参数:
GNetworkX 图

一个无向图。

返回:
nodes生成器

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

抛出:
NetworkXNotImplemented

如果输入的图不是无向图。

另请参见

is_biconnected
articulation_points
biconnected_component_edges
k_components

此函数是 k=2 的特殊情况

bridge_components

与此函数类似，但使用 2-边连通性而不是 2-节点连通性来定义。

注意

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

参考文献

[1]

Hopcroft, J.; Tarjan, R. (1973). “Efficient algorithms for graph manipulation”. Communications of the ACM 16: 372–378. doi: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))

在本页