我不明白这个算法如何告诉我一个图是否是双连通的

Question

我正在为即将到来的面试做一些练习，我发现一个练习题要求 O(V+E) 算法来判断一个图是否是双连通的。 This 来自普林斯顿的页面说，如果一个图没有关节顶点，那么它是双连通的，其中关节顶点是一个顶点，它的移除会增加连通分量的数量（因为双连通图应该有一个连通分量）。

此问题的一个常见解决方案是使用附加跟踪来执行 DFS，以查看是否有任何顶点是关节顶点。 This 页面说顶点是关节顶点 if

• V是根节点至少有2 children 或者
• V 有一个 child 无法到达 V
的祖先

但是，根节点的条件对我来说没有意义。这是双连通图的示例：

如果我们选择任何一个节点作为根，它们都有 2 个或更多 children，因此将是一个关节顶点，从而使图不是双连通的。这是查找连接组件的常用算法，所以假设我误解了一些东西。我实际上需要什么来检查根节点以查看图是否是双连通的？

Answer 1

你应该进行 depth-first 搜索，这意味着 DFS 树总是看起来像

1   4
|   |
2---3

因为你无法探索 1--4 link，直到你探索完从 2 可以到达的所有事物而不经过 1，并且你不会添加 1--4 因为它与树的边缘形成一个循环。这棵树中没有节点有两个children（1是根）。