圖論-劉汝佳.ppt

《圖論-劉汝佳.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、一些圖論算法劉汝佳目錄DFS相關(guān)算法二分圖相關(guān)算法網(wǎng)絡流相關(guān)算法最小樹形圖DFS相關(guān)算法基本應用找連通分量二分圖判定無向圖的連通性有向圖的連通性時間戳和邊分類時間初始化為0，最大值為2

2、E

3、。數(shù)值本身無意義，但大小關(guān)系有意義voidPREVISIT(intu){pre[u]=++dfs_clock;}voidPOSTVISIT(intu){post[u]=++dfs_clock;}無向圖：只有樹邊和反向邊無向連通圖的割頂DFS森林一定只有一棵樹。樹根是不是割頂呢？不難發(fā)現(xiàn)，當且僅當它有兩個或更多的兒子時，它才是割頂—

4、—無向圖只有樹邊和反向邊，不存在跨越兩棵子樹的邊。對于其他點，情況就要復雜一些。我們有下面的定理：定理：在無向連通圖G的DFS樹中，非根結(jié)點u是G的割頂當且僅當u存在一個兒子w，使得w及其所有后代都沒有反向邊連回u的祖先（連回u不算）。定理的證明u存在一個兒子w，使得w及其所有后代都沒有反向邊連回u的祖先（連回u不算）。為了方便起見，我們設low(u)為u及其后代所能連回的最早的祖先的pre值，則定理中的條件就可以簡寫成：結(jié)點u存在一個兒子w，使得low(w)>=pre(u)。若low(w)>pre(u)，即w最多只

5、能連回自己，則只需刪除(u,w)一條邊就可以讓圖G非連通了。滿足這個條件的邊稱為橋（bridge）low函數(shù)本身的計算voiddfs(intu,intfa){//u的父親結(jié)點是fa，初次調(diào)用fa=-1low[u]=pre[u]=++dfs_clock;//初始化low(u)intd=G[u].size();for(inti=0;i

6、n(low[u],low[w]);//用后代的low函數(shù)更新}elseif(w!=fa)low[u]=min(low[u],pre[w]);//用反向邊更新}}雙連通與邊-雙連通如果一個無向連通圖沒有割頂，稱它是點-雙連通的，一般簡稱雙連通（biconnected）；如果沒有橋，稱它是邊-雙連通（edge-biconnected）的。點-雙連通的等價條件：任意兩點存在兩條“點不重復”的路徑。這個要求等價于任意兩條邊都在同一個簡單環(huán)中，因此內(nèi)部無割頂。邊-雙連通的等價條件：任意兩點存在兩條“邊不重復”的路徑。這個要求要

7、低一點，只需要每條邊都至少在一個簡單環(huán)中，因此所有邊都不是橋。點/邊-雙連通分量下圖有兩個點-雙連通分量：{1,2,3}和{3,4,5}，但只有一個邊-雙連通分量：{1,2,3,4,5}。算法邊-雙連分量：兩步走，先求出所有的橋，然后再做一次dfs染色。因為邊-雙連通分量是沒有公共頂點的，所以只要在第二次dfs的時候保證不經(jīng)過橋即可。點-雙連通分量：Tarjan算法（見后）voiddfs(intu,intfa){low[u]=pre[u]=++dfs_clock;intd=G[u].size();for(inti=0

8、;i=pre[u]){//u是割頂或者根，意味著一個bcc的終止++bcc_cnt;printf("BCC%d,containing(%d,%d):",bcc_cnt,u,w

9、);paire;do{e=S.top();S.pop();printf("%d%d",e.first,e.second);}while(e!=mp(u,w));}}elseif(w!=fa)low[u]=min(low[u],pre[w]);}}有向圖的強連通分量理想情況：依次從I,C,D…出發(fā)DFS，則每次DFS恰好得到一個SCCKosaraju算法執(zhí)行兩次DFS，其中第一次DFS得到了關(guān)于各個SCC拓撲順序的有關(guān)信息，而第二次DFS按照這個拓撲順序的逆序進行DFS，從而把每個SCC分開。第一

10、步：對G進行普通的DFS，把各個結(jié)點按照訪問結(jié)束時間從后往前的順序放入列表list中。第二步：計算G的轉(zhuǎn)置GT（即把所有有向邊(u,v)變?yōu)橛邢蜻?v,u)）第三步：對GT進行DFS，其中主循環(huán)中按下標從小到大的順序依次考慮list中的各個結(jié)點，則每次dfs將會得到一個不同的SCC。圓桌騎士每次圓桌會議由至少3個騎士參加，騎士的數(shù)目必須為奇數(shù)，