biconnected_component_edges#

biconnected_component_edges(G)[源代码]#

返回边列表的生成器,为输入图形的每个双连接组件返回一个列表。

双连接组件是最大的子图,这样移除节点(以及该节点上的所有边)不会断开子图。请注意,节点可能是多个双连接组件的一部分。这些节点是关节点或切割顶点。但是,每个边都属于一个且仅属于一个双连接组件。

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

参数
G网络X图表

无向图。

返回
edges列表生成器

边缘列表的生成器,每个双分量对应一个列表。

加薪
NetworkXNotImplemented

如果输入图不是无向的。

笔记

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

工具书类

1

Hopcroft,J.;Tarjan,R.(1973)。”图形处理的有效算法”。ACM通信16:372–378。内政部: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