ACM算法設(shè)計(jì)與競賽II-3課.ppt

1、2020/8/2,ACM算法設(shè)計(jì)與競賽II,1/66,第6章 圖論算法,6.1 最短路徑 6.2 最小生成樹 6.3 最大匹配匈牙利算法 6.4 最優(yōu)權(quán)匹配問題 6.5 割點(diǎn)、割邊以及連通分量 6.6 網(wǎng)絡(luò)流 6.7 實(shí)例分析 6.8 小結(jié),2020/8/2,ACM算法設(shè)計(jì)與競賽II,2/66,6.5 割點(diǎn)、割邊以及連通分量,6.5.1 理論基礎(chǔ) 6.5.2 求割點(diǎn) 6.5.3 求強(qiáng)連通分量,2020/8/2,ACM算法設(shè)計(jì)與競賽II,3/66,6.5.1 理論基礎(chǔ),1. 時間戳 dfni表示結(jié)點(diǎn)i是第dfni 個被訪問到的結(jié)點(diǎn)。 時間戳在遍歷時能記錄下許多有用的信息，所以是很多圖算法的基礎(chǔ)。

2、,2020/8/2,ACM算法設(shè)計(jì)與競賽II,4/66,6.5.1 理論基礎(chǔ)（續(xù)）,void dfs(v) dfnv = +times; /記錄訪問結(jié)點(diǎn)的時間戳 visitv = 1; for 尋找一個v的相鄰結(jié)點(diǎn)u if （visitu = 0）then dfs(u); ,2020/8/2,ACM算法設(shè)計(jì)與競賽II,5/66,6.5.1 理論基礎(chǔ)（續(xù)1）,2. 割點(diǎn) 割點(diǎn)：無向連通圖中的割點(diǎn)指這樣一個頂點(diǎn)，如果刪除它，圖就會被分割成至少兩個分離的子圖。 割點(diǎn)也稱為關(guān)節(jié)點(diǎn)（articulation point）。 圖6-3中頂點(diǎn)0、4、5、6、7和11為割點(diǎn)。 割邊（橋）：圖中的割邊（橋）是這

3、樣一條邊，若刪除它，則將連通圖分離成兩個斷開的子圖。,2020/8/2,ACM算法設(shè)計(jì)與競賽II,6/66,6.5.1 理論基礎(chǔ)（續(xù)2）,3. 強(qiáng)連通分量 強(qiáng)連通圖：在有向圖G中,若對于任意兩個頂點(diǎn)u,v,都存在從u到v的通路,也存在從v到u的通路,則稱G為強(qiáng)連通圖。 強(qiáng)連通分量：有向圖G的極大強(qiáng)連通子圖稱為G的強(qiáng)連通分量。 例:圖6-4。,2020/8/2,ACM算法設(shè)計(jì)與競賽II,7/66,6.5.2 求割點(diǎn),1. 基本思想 深度優(yōu)先生成樹 樹邊,回邊 對樹中任一頂點(diǎn)v而言,其孩子結(jié)點(diǎn)為在它之后搜索到的鄰接點(diǎn),而其雙親結(jié)點(diǎn)和由回邊聯(lián)結(jié)的祖先結(jié)點(diǎn)是在它之前搜索到的鄰接點(diǎn)。,2020/8/2,

4、ACM算法設(shè)計(jì)與競賽II,8/66,6.5.2 求割點(diǎn)（續(xù)）,兩類割點(diǎn)的特性： （1）若生成樹的根有兩棵或兩棵以上的子樹，則此根結(jié)點(diǎn)必為割點(diǎn)。 （2）若生成樹中某個非葉結(jié)點(diǎn)v，其某棵子樹的根和子樹中的其他結(jié)點(diǎn)均沒有指向v的祖先的回邊，則v為割點(diǎn)。,2020/8/2,ACM算法設(shè)計(jì)與競賽II,9/66,6.5.2 求割點(diǎn)（續(xù)1）,定義： low(v) = mindfnv,loww,dfnk|w是頂點(diǎn)v在深度優(yōu)先生成樹上的孩子結(jié)點(diǎn)；k是頂點(diǎn)v在深度優(yōu)先生成樹上由回邊聯(lián)結(jié)的祖先結(jié)點(diǎn)。 若對于某個頂點(diǎn)v，存在孩子結(jié)點(diǎn)w且low(w)=dfnv,則該頂點(diǎn)v必為割點(diǎn)。 因?yàn)楫?dāng)w是v的孩子結(jié)點(diǎn)時， low(w)=dfnv,表明w及其子孫均無指向v的祖先的回邊