algorithm - 使用 DFS 和双分量算法查找关节点

Question

我在实现(不是代码)DFS 时遇到问题，该 DFS 结合了双分量算法来查找图中的接合点，该算法在我的计算机科学讲座中介绍过，但我没有掌握实现。 (只是为了澄清，我知道如何实现 DFS)让我解释一下:我们得到了一张图，我们必须执行 DFS 以找到所有关节点，使用回数和 DFS 数。我的主要问题是使用给定的算法找到每个节点的后退编号。

我们得到了一个教程作为实现算法的练习，我完成了但我不知道它是否正确。有人可以检查我是否正确完成并在可能的情况下纠正我。教程题如下

Use the algorithm done in class to do a depth-first search tree of the algorithm. For each vertex find:

• the dfs-number

• the back number

• whether it is an articulation point The algorithm and My solution is: Thanks. Hope someone can help

Answer 1

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