双连通分量边

biconnected_component_edges(G)

返回一个边的列表的生成器，输入图的每个双连通分量对应一个列表。

双连通分量是最大的子图，移除其中任何一个节点（以及与其关联的所有边）都不会使子图断开连接。注意，节点可能属于多个双连通分量。这些节点是关节（articulation points）或割点（cut vertices）。然而，每条边只属于一个双连通分量。

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

参数：

GNetworkX Graph NetworkX 图

一个无向图。

返回：

edgesgenerator of lists 列表生成器

边的列表生成器，每个双连通分量对应一个列表。

抛出：

NetworkXNotImplemented

如果输入图不是无向图。

另见

is_biconnected

biconnected_components

articulation_points

注释

查找关节和双连通分量的算法使用非递归深度优先搜索（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.barbell_graph(4, 2)
>>> print(nx.is_biconnected(G))
False
>>> bicomponents_edges = list(nx.biconnected_component_edges(G))
>>> len(bicomponents_edges)
5
>>> G.add_edge(2, 8)
>>> print(nx.is_biconnected(G))
True
>>> bicomponents_edges = list(nx.biconnected_component_edges(G))
>>> len(bicomponents_edges)
1