第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全,請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問(wèn)題,去搜搜看,總會(huì)有你想問(wèn)的

數(shù)據(jù)結(jié)構(gòu)和算法分析中割點(diǎn)問(wèn)題.

數(shù)據(jù)結(jié)構(gòu)和算法分析中割點(diǎn)問(wèn)題.

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]不成立,那么就是WV之前的某節(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)。


查看完整回答
反對(duì) 回復(fù) 2018-10-29
  • 1 回答
  • 0 關(guān)注
  • 914 瀏覽
慕課專欄
更多

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)