在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 。


  回復  更多評論