articulation_points

articulation_points(G)

生成图的关节点或割点。

关节点或割点是指移除该节点（及其所有关联边）后，图的连通分量数量增加的任何节点。没有关节点的无向连通图是双连通的。关节点属于图中的多个双连通分量。

请注意，根据惯例，一个双点视为一个双连通分量。

参数:

GNetworkX 图

一个无向图。

生成:

节点

图中的一个关节点。

抛出:

NetworkXNotImplemented

如果输入图不是无向图。

另请参见

is_biconnected

biconnected_components

biconnected_component_edges

注释

查找关节点和双连通分量的算法使用非递归深度优先搜索（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
>>> 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