我正在阅读有关在图表中查找接合点的算法。
When we are in vertex u and v is its neighbor, then if dfs_low(v) >= dfs_num(u) then u is a cut vertex
dfs_num(i) 在 dfs 中对顶点进行编号。
dfs_low(i) 告诉除其父节点之外从 i 可到达的编号最小的顶点。
我想知道该算法如何适用于 3 节点循环。 (看起来像一个三角形)。
运行这个算法，我得到(其中 i = 0, 1, 2)
dfs_num(i) = i
dfs_num(i) = 0
这将返回 0 作为切割顶点，这显然不是关节点。 我相信我在这里有一些误解。有人可以澄清一下吗？
最佳答案
根是一个特例，因为它没有父节点。如果根在 DFS 树中有多个 child ，则它是一个关节点。一个非根节点 v 是一个关节点，当且仅当它有一个没有后边指向 v 的祖先的子树。
关于algorithm - 使用 dfs_low 和 dfs_num 寻找发音点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26550624/