articulation_points

articulation_points(G)

生成图形的关节点或切割顶点。

关节点或切割顶点是任何节点，其移除（连同其所有入射边）会增加图中连接组件的数量。无向连通图是一个双连通图。关节点属于图形的多个双连接组件。

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

参数

G网络X图表

无向图。

产量

结点

图中的一个连接点。

加薪

NetworkXNotImplemented

如果输入图不是无向的。

参见

is_biconnected

biconnected_components

biconnected_component_edges

笔记

查找连接点和双连接组件的算法是使用非递归深度优先搜索（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
>>> len(list(nx.articulation_points(G)))
4
>>> G.add_edge(2, 8)
>>> print(nx.is_biconnected(G))
True
>>> len(list(nx.articulation_points(G)))
0