algorithm - 寻找图的接合点或切割顶点的算法的说明

Question

我已经在网上搜索过，但找不到任何有关用于查找图的所有关节顶点的 DFS 算法的解释。甚至没有维基页面。

翻阅，我从这里开始了解基本情况。 PDF

每个节点都有一个变量，它实际上查看后边并找到离根节点最近和最上面的节点。处理完所有边后就会找到它。

但是我不明白如何在执行 DFS 的过程中在每个节点找到这个 down & up 变量。这个变量到底在做什么？

请解释算法。

谢谢。

Answer 1

寻找关节顶点是DFS的一个应用。

简而言之，

1. 在图上应用 DFS。获取 DFS 树。
2. 较早访问的节点是它到达但较晚访问的那些节点的“父节点”。
3. 如果一个节点的任何子节点没有到其父节点的任何祖先的路径，则意味着删除该节点将使该子节点与图脱节。
4. 有一个异常(exception):树的根。如果它有多个 child ，那么它就是一个关节点，否则不是。

第 3 点本质上意味着这个节点是一个关节点。

现在对于一个 child ，这条通往节点祖先的路径将通过它或其任何 child 的后缘。

所有这一切都在这个 PDF 中得到了很好的解释.