在O(E)時(shí)間內(nèi)求出一個(gè)連通無(wú)向圖的所有關(guān)節(jié)點(diǎn)2006-11-21 11:391）首先定義關(guān)節(jié)點(diǎn)：Let G = (V, E) be a connected, undirected graph. An articulation point of G is a vertex whose removal disconnects G.
2）兩個(gè)觀察結(jié)論：
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 。
說(shuō)明：Gπ 代表 G的深度優(yōu)先搜索樹 .. Back Edge : 深度優(yōu)先搜索樹中的邊，如果在探索邊(v,w)時(shí)，w是首次被訪問的，則 邊(v,w)是樹邊.其它的邊就是 回邊.（Back Edge）.
解決辦法：
容易看出，關(guān)鍵問題是怎樣利用 B 結(jié)論 。
(實(shí)際上,一種比較費(fèi)時(shí)的方法是: 利用觀察結(jié)論A ，分別以圖中每個(gè)頂點(diǎn)為根，深搜 N 次，那么就可以逐一判定每個(gè)頂點(diǎn)是不是關(guān)節(jié)點(diǎn))
假設(shè)現(xiàn)在考察的 nonroot vertex的點(diǎn)是 V , 所考察的V的子節(jié)點(diǎn)是 s，那么如何判斷有沒有回邊 (s ,V ) 和有沒有 s 的一個(gè)后裔 W 是 V的祖先呢？
利用深度優(yōu)先搜索時(shí)，直觀的想，當(dāng)搜索完 S的全部子節(jié)點(diǎn)后，S的信息才能收集全面。我們用
P(S)來(lái)表示以 S為根的搜索子樹的信息。
P(S ) = min { P(W1),P(W2),P(W3),P(W4),P(W5)....P(Wn) } ,WI代表S的搜索后裔。
如果Wi沒有回邊，那么P(WI) = Q(WI ) ,后者代表第一次搜索到WI 時(shí)的序號(hào)。如果 WI有回邊(WI , PP) ,那么 P(Wi) = P( PP ) .最后來(lái)判斷 P(S )與Q(V)的大小。
如果 P(S) < Q(V) ，說(shuō)明針對(duì)S ，V肯定不是關(guān)節(jié)點(diǎn) ；
P(S) = Q(V) ,說(shuō)明針對(duì) S，V是關(guān)節(jié)點(diǎn)；
P(S) > Q(V) ,說(shuō)明針對(duì) S，V是關(guān)節(jié)點(diǎn).
至此，我們討論就可以結(jié)束了。下面給出一份偽代碼:
輸入：連通無(wú)向圖 G = （V, E） .
輸出：包含G的所有可能關(guān)節(jié)點(diǎn)的數(shù)組 A[1.......count ] 。
Start：
設(shè)S為起始頂點(diǎn)
for 每個(gè)頂點(diǎn) v ∈V
標(biāo)記 v 未訪問
end for
predfn = 0 ;count = 0 ;rootdegree = 0
dfs(s);
過程 dfs(v )
//注意這個(gè)過程中，把v看成根 ，w是子節(jié)點(diǎn)，不要與上面的文字分析混了 .(這里的w與上面的s同)
標(biāo)記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]賦值，以便為上層提供信息.
// 針對(duì)V的判斷，只需要知道P[w] 和Q[v]即可，對(duì)P[v] 的賦值是為上層提供信息
if(P[w] >= Q[v])
artpoint = true ; // Q[w] <p[v]說(shuō)明有環(huán)路.
}
}
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
參考了 ：算法導(dǎo)論 和 Algorithm Design Techniques and Analysis 。
回復(fù) 更多評(píng)論