c++ - 算法:非铰接顶点

Question

An articulation vertex of a graph G is a vertex whose deletion disconnects G. Let G be a graph with n vertices and m edges. Give a simple O(n + m) algorithm for finding a vertex of G that is not an articulation vertex—i.e. , whose deletion does not disconnect G.

让初始编号。顶点数为n，那么删除一个顶点后，我们应该有n-1条边。 我用dfs遍历图并数数。的顶点。如果计数小于n-1，则它是一个关节顶点，所以我将其添加回来。 否则它不是，我增加了一个计数器。

有什么更好的方法来找到非关节顶点，因为这种方法非常慢并且我需要 O(n+m)。

Answer 1

使用 DFS(深度优先搜索)是一个很好的开始方式，因为它本身已经是 O(V + E)。所以我们的想法是遍历一次图并能够找出它的属性。旁注:每当做图算法时思考循环!

证明关节顶点合理的条件(在DFS的思维方式下):

1. 根节点是一个关节点当且仅当它有多个子节点

2. 叶子从来都不是一个关节点

3. 非叶、非根节点 u 是一个接合点iff 没有非树边位于上面u 来自 u 的某个子级下面的子树

这涵盖了所有情况:根节点、叶节点以及其间的任何其他节点。

---

对于非关节顶点，我们只需要找到证明相反的条件:

1. 根节点是一个非关节点当且仅当它有一个子节点
2. 叶子始终是非关节点
3. 非叶、非根节点 u 是一个非铰接点iff上面有一个非树边u 来自 u
某个子级下面的子树

数字3可以理解为:如果两个 split 树之间通过节点u存在另一个连接，又名一个循环。

---

Here is some articulation vertex code 。您可能想要调整它。