03年01月25日極大強連通子圖求子圖

1、求極大強連通子圖有向圖的深度優(yōu)先搜索dfs 有向圖的dfs本質(zhì)上近似無向圖，區(qū)別在于搜索只能順邊的方向去進行(有向邊，簡稱弧)。有向圖中的弧根據(jù)被檢查情況可有4種，一條未檢查的弧(U,W)可按如下4種情況，分類歸劃成(其中2、3、4，所述的三種情況中，設(shè)W已訪問過)： 1W是未訪問過的點，(U,W)歸入樹枝弧。 2W是U的已形成的dfs森林中直系后代點，則(U,W)稱為前向弧。 3W是U的已形成的dfs森林中直系祖先點，則(U,W)稱為后向弧。 4U和W在已形成的dfs森林中沒有直系上下關(guān)系，并且有dfn(W)dfn(U)，則稱(U,W)是橫叉弧。1W是未訪問過的點，(U,W)歸入樹枝弧。 2

2、.W是U的已形成的dfs森林中直系后代點，則(U,W)稱為前向弧。 無論(U,W)是樹枝弧還是前向弧，dfn(W)dfn(U)。細分一下，樹枝邊總使搜索導(dǎo)向一個新的(未訪問)點，且dfn(U)+1dfn(W)。3 W是U的已形成的dfs森林中直系祖先點，則(U,W)稱為后向弧。 4 U和W在已形成的dfs森林中沒有直系上下關(guān)系，并且有dfn(W)dfn(U)，則稱(U,W)是橫叉弧。 注意沒有dfn(W)dfn(U)這種類型的橫叉弧。因為dfs搜索只能從左到右逐條樹枝地進行。無論(U,W)是后向弧(W的所有關(guān)聯(lián)邊未完全檢查)還是橫叉弧(W的所有關(guān)聯(lián)邊完全檢查)，dfn(W)dfn(U)。V1V

3、2V3V4V5V6V71234567V1V2V3V4V5V6V71234567V1V2V3V4V5V6V7樹枝弧前向弧后向弧橫叉弧一個有向圖，它的每一個頂點代表某籃球隊的一個隊員，它的弧代表的意思是：如果有一條從Vi出發(fā)而指向Vj的弧(i，j)，就表示隊員Vi能夠通知Vj。一個有向圖，它的每一個頂點代表某籃球隊的一個隊員，它的弧代表的意思是：如果有一條從Vi出發(fā)而指向Vj的弧(i，j)，就表示隊員Vi能夠通知Vj。 問這張有向圖至少能劃分幾個最大子圖，這些子圖上的所有隊員能相互通知(包括子圖僅含一個隊員，表示自己通知自己)。 為了在dfs森林的基礎(chǔ)上找強分支子樹的根，我們引入了頂點U的標值函數(shù)

4、LOWLINK(U)： LOWLINK(U)mindfn(U)，dfn(W) 其中W是從U或U的后代點出發(fā)用一條后向弧或橫叉弧所能到達的同一強連通分支中的頂點。LOWLINK(U)正是U所處的強分支中從U出發(fā)先用樹枝弧、前向弧，最后用后向弧或橫叉弧到達的dfn最小的頂點的序值。而對于強分支的根ri顯然有LOWLINK (ri)=dfn( ri)(1,1)(2,2)(3,1)(4,4)(5,4)(6,6)(7,7)(10,10)(8,7)(9,9)(11,11)(12,12)V1V2V3V4V6V5V7V8V9V10V11V12樹枝弧前向弧后向弧橫叉弧(1,1)(2,2)(3,3)(3,1)V1

5、V3V2(4,4)V4(5,5)(5,4)V6( )V6V4(2,1)V1V2V3V4V6V5V7V8V9V10V11V12樹枝弧前向弧后向弧橫叉弧(1,1)(2,1)(3,1)V1V3V2(4,4)(5,4)( )V6V4(6,6)V5( )V5V1V2V3V4V6V5V7V8V9V10V11V12樹枝弧前向弧后向弧橫叉弧(1,1)(3,1)(4,4)(5,4)( )V6V4(2,1)( )V1V3V2( )V5(6,6)V1V3V2V1V2V3V4V6V5V7V8V9V10V11V12樹枝弧前向弧后向弧橫叉弧(1,1)(3,1)(4,4)(5,4)( )V6V4(2,1)( )V1V3V2(7,7)(8,8)(8,7)( )V7V8(9,9)( )V9( )V5(6,6)V7V8V9(10,10)( )V12V12V1V2V3V4V6V5V7V8V9V10V11V12樹枝弧前向弧后向弧橫叉弧(1,1)(3,1)(4,4)(5,4)( )V6V4(2,1)( )V1V3V2(7,7)(8,7)( )V7V8(9,9)( )V9( )V5(6,6)(10,10)( )V12(11,11)V10( )V10(12,12)V11( )V11V1V2V3V4V6V5V7V8V9V10V11V12樹枝弧前向弧后向弧橫叉弧(1,1)(3,1)(4,4)(5,4)( )