algorithm - 关节点忽略通向直接父级的边的反转

Question

来自普林斯顿算法类(class)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):

• pre[v] is the DFS-preorder index of v, in other words, the depth of that vertex in the DFS tree;
• low[v] is the lowest depth of neighbors of all descendants of v (including v itself) in the DFS tree

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

可以在此处找到进一步的解释:link-2