articulation point ignores reverse of edge leading to direct parent

Question

From the algorithm course of Princeton Articulation Point, the articulation algorithm dfs() ignores reverse of edge leading to v. But why cannot we use the backward edge when it points to direct parent? Please refer to this part of code

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

The full code is below.

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;
}

score 0 · Answer 1 · answered Oct 01 '19 at 17:24

By the definition of this algorithm (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

So during the call DFS(G, u, v) we should not check reverse edge (v->u), because the vertex u is an ancestor of v, so it should not be considered in low[v] calculation.

Further explanation could be found here: link-2

articulation point ignores reverse of edge leading to direct parent

1 Answers1