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

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

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

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

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