使用 DFS 和 bi-components 算法查找关节点

Question

我在实施（不是代码）DFS 时遇到问题，该 DFS 结合了 bi-components 算法来查找图中的连接点，该算法在我的计算机科学讲座中介绍过，但我没有掌握实施。 （只是为了澄清，我知道如何实施 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 树中有两个或更多子节点时，根才是关节点。