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