查找非所需顶点中的曲线图

Question

是否有任何已知的算法是： 对于给定的连通图ģ通过该顶点可以同时被去除的顶点的V的边缘Ëdetrmines列表和列表中定义图表仍将连接？

感谢您的帮助。

N.B：

1. 我通过连通图，每两个顶点V1和V2 在它们之间的路径的意思。
2. 算法的复杂性是一个问题

Answer 1

这是一个众所周知的问题。这些顶点被称为图形关节点。可以使用深度优先搜索在O(V + E)中找到它们。很容易找到这种算法的描述（例如，这里：http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/）。