图论算法之：割点

时间：2010-09-24 来源：kaiserhui

源码：

文件:	AdjList.rar
大小:	255KB
下载:	下载

搞了一下午，终于把割点算法弄明白了，总结一下吧！正在学习C++，所以用C++的类思想实现了一下，确实变的很模块化！求割点有两种方法：1.笨方法，遍历每个点，将每个点都从图中挖出去，之后对图进行遍历，如果遍历不完整就证明挖出去的这个点为割点。 2.按照定理的方法，定理的内容是这样的：Let v be a nonroot vertex of Gπ. Prove that v is an articulation point of G if and only if v has a child s such that there is no back edge from s or any descendant of s to a proper ancestor of v。大概意思就是：对每个点维持用两个数组，P，Q，P记录的是此点通过回退边能够访问的最小点，Q记录的是此点在遍历过程中被访问的次序。通过比较Q[v]和P[v's child]，如果P[v's child]>=Q[v]则，v为一个割点，否则v不是割点。除此之外，还有其他需要注意的（主要针对方法2）：求关键点（即割点，下同）算法中，对于关键点的判断有两种可能：1，根节点有两棵或以上的子树，那么根就是关键点。 2，指向父结点的边不算回边（其实算也应该无所谓，如果有回退边指向更小的自然会被覆盖掉，只是能稍微的简便运算量）一下是伪代码：

Start：
设S为起始顶点
for 每个顶点 v ∈V
      标记 v 未访问
end for
predfn = 0 ;count = 0 ;rootdegree = 0
dfs(s);

过程 dfs(v )
//注意这个过程中，把v看成根，w是子节点，不要与上面的文字分析混了 .(这里的w与上面的s同)

标记v已访问；artpoint = false ;predfn = predfn +1 ;
Q[v] =predfn ; P[v] = predfn ;
for(每条边 (v,w )∈E) {
         if (v,w)为树边 {
                dfs(w)
                if(v == s )then {
                 rootdegree ++ ;
                 if(rootdegree == 2 ) then artpoint = true ;
                }
                else {
                        P[v] = min{ P[v] , P[w]} ; // 给P[V]赋值，以便为上层提供信息.

                      // 针对V的判断，只需要知道P[w] 和Q[v]即可，对P[v] 的赋值是为上层提供信息

              if(P[w] >= Q[v])
                                artpoint = true ; // Q[w] <p[v]说明有环路.

                    }
       }
       else if(v,w) is back edge {
      P[v] = min{ P[v], Q[w] } // P[W]没有被有效赋值

       }
else {/*do nothing*/}
end for

if(artpoint ){
    count ++ ;
    A[count] = v;
}


}

参考文章：http://www.cnblogs.com/feature/articles/1802640.html（C实现的源码） http://winterlegend.blog.hexun.com/24681750_d.html http://hi.baidu.com/js_zheng/blog/item/1aa8480e05ed52c27bcbe1d5.html（理论讲得不错）
http://www.byvoid.com/blog/biconnect/（这篇更不错）