algorithm - 双连通分量

Question

我已经阅读了这个很棒的算法，用于在连接图中找到关节点https://en.wikipedia.org/wiki/Biconnected_component

在算法中，为每个节点计算低点，这意味着给定节点的所有后代的邻居的最低深度。

这个低点如何帮助找到关节点以及为什么要计算它？尤其是非根节点。我想要算法中低点的意义。

标签： algorithmdata-structures

Answer 1

我给出两种解释：

1. 基本上，顶点 V1 的低点是另一个顶点的深度，如果 DFS 距离 V1 更远，并且如果您无法返回在 V1 之前发现的任何顶点，则删除 V1 会拆分图形。

2. 请注意，如果在访问了所有顶点子节点后，您还没有找到一个低点小于顶点的子节点，这意味着没有循环边，删除该顶点会拆分图。