查找非所需頂點中的曲線圖

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/）。