1 无向图断开点

如果移除无向连通图中的顶点（以及穿过该顶点的边）会断开该图，则该顶点是一个连接点（或切割顶点Cutting Point）。连接点表示连接网络中的漏洞–单点故障会将网络拆分为两个或多个组件。它们对于设计可靠的网络很有用。
对于断开连接的无向图，连接点是顶点移除，这会增加连接组件的数量。
上面和下面是一些用红色包围关节点的示例图。

 

2 如何找到给定图形中的所有连接点？

一种简单的方法是逐个删除所有顶点，然后查看删除顶点是否会导致图断开连接。下面是连接图的简单方法步骤。
1） 对于每个顶点v，执行以下操作
a） 从图形中删除v
b） 查看图表是否保持连接（我们可以使用BFS或DFS）
c） 将v添加回图形
对于用邻接表表示的图，上述方法的时间复杂度为O（V*（V+E））。

3 查找所有关节点（AP）的O（V+E）算法

其想法是使用DFS（深度优先搜索）。在DFS中，我们以称为DFS树的树形式跟踪顶点。在DFS树中，如果v是由u发