时间戳

首页 > 解决方案 > 关节点忽略导致直接父级的边缘的反向

algorithm - 关节点忽略导致直接父级的边缘的反向

问题描述

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

标签： algorithmgraph

解决方案

根据该算法的定义（link-1）：

  • pre[v] 是 v 的 DFS-preorder 索引，换句话说，是 DFS 树中那个顶点的深度；
  • low[v] 是 DFS 树中 v 的所有后代（包括 v 本身）的邻居的最低深度

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

进一步的解释可以在这里找到：link-2

推荐阅读