慕碼人8056858
2018-10-09 07:20:48
void AssignNum(vertex V){ vertex M; Num[V] = counter++; Visitied[V] = True; for each W adjanct to V if(!Visited[W]) { Parent[W] = V; AssignNum[W]; }}void AssignLow(vertex V){ vertex W; Low[V] = Num[V]; for each W adjanct to V { if(Num[W]>Num[V]) { AssignLow(W); if(Low[W]>=Num[V])//這里不就一直成立,每個(gè)點(diǎn)都是割點(diǎn) printf("V is an articulation point"); Low[V] = Min(Low[V],Low[W]); } else if(Parent[V]!=W)//V怎么會(huì)臨接到W呢? Low[V] = Min(Low[V],Nun[W]); }}數(shù)據(jù)結(jié)構(gòu)書上將割點(diǎn)的部分,變量的意義在圖上。我不明白的是:assignlow中每個(gè)Low(W)=Num(W);而Num(W)是遞增的,那么assignlow中判斷就一直成立,每個(gè)都是割點(diǎn)啊、還有就是后面的那個(gè)特殊情況沒(méi)有理解。請(qǐng)大家?guī)兔χv解一下。謝謝!
1 回答

一只甜甜圈
TA貢獻(xiàn)1836條經(jīng)驗(yàn) 獲得超5個(gè)贊
if(Low[W] >= Num[V])
只有在樹的情況下成立,而樹的每個(gè)節(jié)點(diǎn)都是割點(diǎn),失去任一個(gè)節(jié)點(diǎn)都會(huì)導(dǎo)致不連通。如果Low[W] >= Num[V]
不成立,那么就是W
和V
之前的某節(jié)點(diǎn)也有邊相連,成環(huán),而去掉環(huán)上任一節(jié)點(diǎn)不會(huì)導(dǎo)致不連通。
形象上的,每個(gè)割點(diǎn)分隔了兩個(gè)或者更多的點(diǎn)集,這兩部分點(diǎn)集除了割點(diǎn)外是不連通的。AssignNUm
將點(diǎn)集按樹的層次劃分,AssignLow
則是將把連通的點(diǎn)集攢聚在一起。最終如果某點(diǎn)分割的兩邊點(diǎn)集不連通,即Low[W] >= Num[V]
,從W
追溯到的最高層次的點(diǎn)不大于Num[V]
,則此點(diǎn)為割點(diǎn)。
添加回答
舉報(bào)
0/150
提交
取消