亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

為了賬號安全,請及時綁定郵箱和手機立即綁定
已解決430363個問題,去搜搜看,總會有你想問的

數據結構和算法分析中割點問題.

數據結構和算法分析中割點問題.

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])//這里不就一直成立,每個點都是割點                printf("V is an articulation point");            Low[V] = Min(Low[V],Low[W]);        }        else        if(Parent[V]!=W)//V怎么會臨接到W呢?            Low[V] = Min(Low[V],Nun[W]);    }}數據結構書上將割點的部分,變量的意義在圖上。我不明白的是:assignlow中每個Low(W)=Num(W);而Num(W)是遞增的,那么assignlow中判斷就一直成立,每個都是割點啊、還有就是后面的那個特殊情況沒有理解。請大家幫忙講解一下。謝謝!
查看完整描述

1 回答

?
一只甜甜圈

TA貢獻1836條經驗 獲得超5個贊

if(Low[W] >= Num[V])只有在樹的情況下成立,而樹的每個節點都是割點,失去任一個節點都會導致不連通。如果Low[W] >= Num[V]不成立,那么就是WV之前的某節點也有邊相連,成環,而去掉環上任一節點不會導致不連通。

形象上的,每個割點分隔了兩個或者更多的點集,這兩部分點集除了割點外是不連通的。AssignNUm將點集按樹的層次劃分,AssignLow則是將把連通的點集攢聚在一起。最終如果某點分割的兩邊點集不連通,即Low[W] >= Num[V],從W追溯到的最高層次的點不大于Num[V],則此點為割點。


查看完整回答
反對 回復 2018-10-29
  • 1 回答
  • 0 關注
  • 906 瀏覽

添加回答

舉報

0/150
提交
取消
微信客服

購課補貼
聯系客服咨詢優惠詳情

幫助反饋 APP下載

慕課網APP
您的移動學習伙伴

公眾號

掃描二維碼
關注慕課網微信公眾號