一尘不染

查找图的关节点或切点的算法的说明

algorithm

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

通过阅读,我从这里开始了解基本事实。PDF格式

每个节点上都有一个变量,该变量实际上是在查看后边缘并找到朝向根节点的最近节点和最高节点。处理完所有边缘后,将发现它。

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

请说明算法。

谢谢。


阅读 609

收藏
2020-07-28

共1个答案

一尘不染

查找发音顶点是DFS的一种应用。

简而言之,

  1. 在图表上应用DFS。获取DFS树。
  2. 较早访问的节点是该节点到达并较后访问的那些节点的“父”节点。
  3. 如果节点的任何子节点都没有到其父节点的任何祖先的路径,则意味着删除该节点将使该子节点与图不相交。
  4. 有一个例外:树的根。如果它有多个孩子,则这是一个衔接点,否则就没有。

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

现在,对于一个孩子而言,通往节点祖先的路径将是来自其或其任何子节点的后端。

这一切都在本PDF中得到了很好的解释。

2020-07-28