源码：
 |
| 文件: | AdjList.rar |
| 大小: | 263KB |
| 下载: | 下载 |
|
搞了一下午，终于把割点算法弄明白了，总结一下吧！正在学习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，指向父结点的边不算回边
以上标红字的两点非常关键，写成代码形式为：
while(p){
if(!visited[p->adjvex]){
if(i == ROOT){
if(++rootson > 1)
ArtPoint[i] = true;
}
Tarjan_cut_bridge(visited, p->adjvex, i);
low[i] = Min(low[i], low[p->adjvex]);
if(i!=ROOT&&low[p->adjvex]>=dfn[i])
ArtPoint[i] = true;
if(low[p->adjvex]>dfn[i])
Bridge[i] = p->adjvex;
}else if(p->adjvex!=father){
low[i] = Min(low[i], dfn[p->adjvex]);
}
p = p->next;
}
|
一下是伪代码：
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]
}
}
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实现的源码）
阅读(5644) | 评论(1) | 转发(0) |
