使用DFS和双组分算法查找关节点

Question

我在执行（不是代码）DFS时遇到了麻烦，该算法结合双组分算法来查找图中的关节点，该算法在我的计算机科学讲座中提出，没有把握实施。 （只是为了澄清我知道如何实现DFS）让我解释一下：我们给出了一个图表，我们必须执行一个DFS来查找所有关节点，使用后面的数字和DFS号码。我的主要问题是使用给定的算法找到每个节点的背部编号。

我们给了一个教程作为练习来实现算法，我做了它，但我不知道它是否正确。有人可以检查我是否做得正确，如果可能的话纠正我。教程问题如下

使用类中的算法做一个 深度优先搜索树的算法。对于每个顶点发现：

•在DFS-数

•背号

•它是否是一个关节点 算法和我的解决办法是： 感谢。希望有人可以帮助

Answer 1

你算法几乎是正确的。处理不当的唯一情况是根：当且仅当在dfs树中有两个或更多子项时，根才是关节点。