biconnected_component_edges#

biconnected_component_edges(G)[source]#

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

双连通分量是最大子图，移除一个节点（及其所有关联边）不会使子图断开。注意，一个节点可能属于多个双连通分量。这些节点是关节点，或割点。然而，每条边属于一个且仅属于一个双连通分量。

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

Parameters:

GNetworkX 图: 一个无向图。

Returns:

edges列表生成器: 生成器，包含每个双连通分量的边的列表。

Raises:

NetworkXNotImplemented: 如果输入图不是无向图。

See also

is_biconnected
biconnected_components
articulation_points

Notes

用于查找关节点和双连通分量的算法实现使用了一个非递归的深度优先搜索（DFS），该搜索记录了回边在DFS树中达到的最高层级。一个节点 n 是关节点当且仅当存在一个以 n 为根的子树，该子树中没有任何后继节点通过回边连接到 n 在DFS树中的前驱节点。通过记录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.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