铰接点忽略通向直接父节点的边的反向

Question

从普林斯顿Articulation Point的算法过程中，衔接算法dfs()忽略了指向v的边缘的反向。但是，当反向边缘指向直接父级时，为什么我们不能使用它？请参考这部分代码

    // **low number - ignore reverse of edge leading to v. Why is this???**
    else if (w != u)
        low[v] = Math.min(low[v], pre[w]);

完整的代码如下。

private void dfs(Graph G, int u, int v) {
    int children = 0;
    pre[v] = cnt++;
    low[v] = pre[v];
    for (int w : G.adj(v)) {
        if (pre[w] == -1) {
            children++;
            dfs(G, v, w);

            // update low number
            low[v] = Math.min(low[v], low[w]);

            // non-root of DFS is an articulation point if low[w] >= pre[v]
            if (low[w] >= pre[v] && u != v) 
                articulation[v] = true;
        }

        // **low number - ignore reverse of edge leading to v. Why is this???**
        else if (w != u)
            low[v] = Math.min(low[v], pre[w]);
    }

    // root of DFS is an articulation point if it has more than 1 child
    if (u == v && children > 1)
        articulation[v] = true;
}

Answer 1

根据此算法的定义(link-1)：

_

• _prev是v的DFS-preorder索引，换句话说，是该顶点在DFS树中的深度；

_

• _

_v是DFS树中v的所有后代(包括v本身)的邻居的最低深度_

因此，在调用DFS(G, u, v)期间，我们不应该检查反向边(v->u)，因为顶点u是v的祖先，因此不应该在low[v]计算中考虑它。

更多解释可以在这里找到：link-2