我已经在网上搜索过,找不到用于查找图的所有关节顶点的DFS算法的任何说明。甚至没有维基页面。
通过阅读,我从这里开始了解基本事实。PDF格式
每个节点上都有一个变量,该变量实际上是在查看后边缘并找到朝向根节点的最近节点和最高节点。处理完所有边缘后,将发现它。
但是我不明白如何在执行DFS的过程中在每个节点上找到这个上下变量。这个变量到底在做什么?
请说明算法。
谢谢。
查找发音顶点是DFS的一种应用。
简而言之,
点3本质上意味着该节点是一个关节点。
现在,对于一个孩子而言,通往节点祖先的路径将是来自其或其任何子节点的后端。
这一切都在本PDF中得到了很好的解释。