在O(E)时间内求出一个连通无向图的所有关节点2006-11-21 11:391）首先定义关节点：Let G = (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G.
2）两个观察结论：
A. The root of Gπ is an articulation point of G if and only if it has at least two children in Gπ.
B. 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 。
说明：Gπ 代表 G的深度优先搜索树 .. Back Edge : 深度优先搜索树中的边，如果在探索边(v,w)时，w是首次被访问的，则 边(v,w)是树边.其它的边就是 回边.（Back Edge）.
解决办法：
容易看出，关键问题是怎样利用 B 结论 。
(实际上,一种比较费时的方法是: 利用观察结论A ，分别以图中每个顶点为根，深搜 N 次，那么就可以逐一判定每个顶点是不是关节点)
假设现在考察的 nonroot vertex的点是 V , 所考察的V的子节点是 s，那么如何判断有没有回边 (s ,V ) 和有没有 s 的一个后裔 W 是 V的祖先呢？
利用深度优先搜索时，直观的想，当搜索完 S的全部子节点后，S的信息才能收集全面。我们用
P(S)来表示以 S为根的搜索子树的信息。
P(S ) = min { P(W1),P(W2),P(W3),P(W4),P(W5)....P(Wn) } ,WI代表S的搜索后裔。
如果Wi没有回边，那么P(WI) = Q(WI ) ,后者代表第一次搜索到WI 时的序号。如果 WI有回边(WI , PP) ,那么 P(Wi) = P( PP ) .最后来判断 P(S )与Q(V)的大小。
如果 P(S) < Q(V) ，说明针对S ，V肯定不是关节点 ；
P(S) = Q(V) ,说明针对 S，V是关节点；
P(S) > Q(V) ,说明针对 S，V是关节点.
至此，我们讨论就可以结束了。下面给出一份伪代码:
输入：连通无向图 G = （V, E） .
输出：包含G的所有可能关节点的数组 A[1.......count ] 。
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;
}
} //for
参考了 ：算法导论 和 Algorithm Design Techniques and Analysis 。
回复 更多评论