割點橋雙連通分量課件

圖論1江川圖論1江川1七橋問題七橋問題2七橋問題七橋問題3七橋問題七橋問題4圖、點、邊G=(V,E)V頂點集E邊集圖的基本概念圖、點、邊圖的基本概念5G=(V,E)有向圖、無向圖無向圖V&Ve={a,b}有向圖VxVe=<a,b>={{a},{a,b}}圖的基本概念G=(V,E)圖的基本概念6G=(V,E)度（入度、出度）環(huán)路徑割圖的基本概念G=(V,E)圖的基本概念7G=(V,E)簡單圖完全圖二分圖平面圖圖的基本概念G=(V,E)圖的基本概念8鄰接矩陣圖的表示鄰接矩陣圖的表示9鄰接表（邊表）圖的表示鄰接表（邊表）圖的表示10判定連通度數(shù)平衡（有向、無向）歐拉環(huán)判定歐拉環(huán)11求解“有邊就走”回溯歐拉環(huán)求解歐拉環(huán)12其他歐拉路混合圖歐拉環(huán)其他歐拉環(huán)13漢密爾頓回路漢密爾頓回路14NP-Complete對于頂點個數(shù)大于2的圖，如果圖中任意兩點度的和大于或等于頂點總數(shù)，那這個圖一定是哈密頓圖。漢密爾頓回路vs歐拉回路漢密爾頓回路NP-Complete漢密爾頓回路15如果一個問題不是多項式時間可解的……1、加強條件，針對特定情況2、減弱要求，求近似解3、降低問題規(guī)模漢密爾頓回路如果一個問題不是多項式時間可解的……漢密爾頓回路16O(n!*n）？狀態(tài)壓縮動態(tài)規(guī)劃要考慮的狀態(tài)：已經(jīng)經(jīng)過哪些點？2^n經(jīng)過點的順序？n！n*nn漢密爾頓回路O(n!*n）？漢密爾頓回路17例：[1,0,1,1,0][3]表示經(jīng)過了1、3和4，并停在3狀態(tài)數(shù)：2^n*n轉(zhuǎn)移：n復(fù)雜度：O（2^n*n^2）POJ3311漢密爾頓回路例：[1,0,1,1,0][3]漢密爾頓回路18Floyd點對間的距離O（n^3）動態(tài)規(guī)劃的思想F[i,j,k]F[i,j]最短路Floyd最短路19Dijkstra單源最短路徑貪心算法尋找未處理的最小的點更新其他點不能有負(fù)權(quán)邊O（V^2）O（VlogV+E）最短路有效的程序員不應(yīng)該浪費很多時間用于程序調(diào)試，他們應(yīng)該一開始就不要把故障引入。Dijkstra最短路有效的程序員不應(yīng)該浪費很20Bellman-Ford對每一條邊進(jìn)行松弛操作，重復(fù)V次：foreachedge(u,v)ifd[v]>d[u]+w(u,v)d[v]=d[u]+w(u,v)允許負(fù)權(quán)邊，可判斷負(fù)權(quán)圈O（VE）最短路Bellman-Ford最短路21SPFAShortestPathFasterAlgorithmBellman-Ford的優(yōu)化用一個隊列存儲被更新的點期望復(fù)雜度：O（kE）最短路SPFA最短路22特殊的圖連通性結(jié)構(gòu)實用序?qū)哟螛涮厥獾膱D樹23最小生成樹Prim算法兩個點集（加入生成樹和未加入生成樹）O（V^2）Kruscal算法按邊權(quán)順序從小到大枚舉O（ElogE）生成樹最小生成樹生成樹24次小生成樹在最小生成樹上添邊生成環(huán)刪邊新的生成樹在最小生成樹上求兩點路徑上最大的邊poj1679生成樹次小生成樹生成樹25拓?fù)渑判?、選擇入度為0的點v2、刪除v和從v出發(fā)的所有邊拓?fù)渑判蚺c強連通分量拓?fù)渑判蛲負(fù)渑判蚺c強連通分量26強連通分量Tarjan算法基于對圖深度優(yōu)先搜索的算法DFN（u）：u搜索到的次序編號（時間戳）Low（u）：u或者u的子樹能夠追溯到的最早的搜索棧中的節(jié)點的次序號。DFN(u)=Low(u)時，以u為根的搜索子樹上所有節(jié)點是一個強連通分量。拓?fù)渑判蚺c強連通分量強連通分量拓?fù)渑判蚺c強連通分量27拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量28拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量29拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量30拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量31拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量32拓?fù)渑判蚺c強連通分量O（V+E）POJ2762拓?fù)渑判蚺c強連通分量O（V+E）33割點v：去掉點v后圖不連通橋/割邊e：去掉邊e后圖不連通雙連通分量：1、（邊）任意去掉一條邊，圖仍連通2、（點）任意去掉一個點，圖仍連通割點、橋、雙連通分量割點v：去掉點v后圖不連通割點、橋、雙連通分量34Tarjan算法求割點在圖的搜索樹中，如果u為割點，當(dāng)且僅當(dāng)滿足下面的條件：1、如果u為樹根，那么u必須有多于1棵子樹2、如果u不為樹根，那么（u,v）為樹枝邊，當(dāng)Low[v]>=DFN[u]時。割點、橋、雙聯(lián)通分量Tarjan算法求割點割點、橋、雙聯(lián)通分量35割點、橋、雙聯(lián)通分量割點、橋、雙聯(lián)通分量36在一個網(wǎng)絡(luò)中，某些點之間可以接發(fā)信息（單向）。問至少增加多少條邊可以使從任一點發(fā)送的信息可以到達(dá)其他所有點？

例題1在一個網(wǎng)絡(luò)中，某些點之間可以接發(fā)信息（單向）。問至少增加多少37強連通分量看做一個點觀察入度為0的點和出度為0的點poj1236

例題1強連通分量看做一個點例題138給定一個有向無環(huán)圖，n個點，m條邊（1<=n<=100000,

0<=m<=1000000），每個點有點權(quán)。要求選擇一條從某個入度為0的點到某個出度為0的點的路徑，使得整個路徑上點的權(quán)值之和最大。

例題2給定一個有向無環(huán)圖，n個點，m條邊（1<=n<=10000039有向無環(huán)圖拓?fù)渑判驁DDPpoj3249例題2有向無環(huán)圖拓?fù)渑判蚶}240謝謝！謝謝！41圖論1江川圖論1江川42七橋問題七橋問題43七橋問題七橋問題44七橋問題七橋問題45圖、點、邊G=(V,E)V頂點集E邊集圖的基本概念圖、點、邊圖的基本概念46G=(V,E)有向圖、無向圖無向圖V&Ve={a,b}有向圖VxVe=<a,b>={{a},{a,b}}圖的基本概念G=(V,E)圖的基本概念47G=(V,E)度（入度、出度）環(huán)路徑割圖的基本概念G=(V,E)圖的基本概念48G=(V,E)簡單圖完全圖二分圖平面圖圖的基本概念G=(V,E)圖的基本概念49鄰接矩陣圖的表示鄰接矩陣圖的表示50鄰接表（邊表）圖的表示鄰接表（邊表）圖的表示51判定連通度數(shù)平衡（有向、無向）歐拉環(huán)判定歐拉環(huán)52求解“有邊就走”回溯歐拉環(huán)求解歐拉環(huán)53其他歐拉路混合圖歐拉環(huán)其他歐拉環(huán)54漢密爾頓回路漢密爾頓回路55NP-Complete對于頂點個數(shù)大于2的圖，如果圖中任意兩點度的和大于或等于頂點總數(shù)，那這個圖一定是哈密頓圖。漢密爾頓回路vs歐拉回路漢密爾頓回路NP-Complete漢密爾頓回路56如果一個問題不是多項式時間可解的……1、加強條件，針對特定情況2、減弱要求，求近似解3、降低問題規(guī)模漢密爾頓回路如果一個問題不是多項式時間可解的……漢密爾頓回路57O(n!*n）？狀態(tài)壓縮動態(tài)規(guī)劃要考慮的狀態(tài)：已經(jīng)經(jīng)過哪些點？2^n經(jīng)過點的順序？n！n*nn漢密爾頓回路O(n!*n）？漢密爾頓回路58例：[1,0,1,1,0][3]表示經(jīng)過了1、3和4，并停在3狀態(tài)數(shù)：2^n*n轉(zhuǎn)移：n復(fù)雜度：O（2^n*n^2）POJ3311漢密爾頓回路例：[1,0,1,1,0][3]漢密爾頓回路59Floyd點對間的距離O（n^3）動態(tài)規(guī)劃的思想F[i,j,k]F[i,j]最短路Floyd最短路60Dijkstra單源最短路徑貪心算法尋找未處理的最小的點更新其他點不能有負(fù)權(quán)邊O（V^2）O（VlogV+E）最短路有效的程序員不應(yīng)該浪費很多時間用于程序調(diào)試，他們應(yīng)該一開始就不要把故障引入。Dijkstra最短路有效的程序員不應(yīng)該浪費很61Bellman-Ford對每一條邊進(jìn)行松弛操作，重復(fù)V次：foreachedge(u,v)ifd[v]>d[u]+w(u,v)d[v]=d[u]+w(u,v)允許負(fù)權(quán)邊，可判斷負(fù)權(quán)圈O（VE）最短路Bellman-Ford最短路62SPFAShortestPathFasterAlgorithmBellman-Ford的優(yōu)化用一個隊列存儲被更新的點期望復(fù)雜度：O（kE）最短路SPFA最短路63特殊的圖連通性結(jié)構(gòu)實用序?qū)哟螛涮厥獾膱D樹64最小生成樹Prim算法兩個點集（加入生成樹和未加入生成樹）O（V^2）Kruscal算法按邊權(quán)順序從小到大枚舉O（ElogE）生成樹最小生成樹生成樹65次小生成樹在最小生成樹上添邊生成環(huán)刪邊新的生成樹在最小生成樹上求兩點路徑上最大的邊poj1679生成樹次小生成樹生成樹66拓?fù)渑判?、選擇入度為0的點v2、刪除v和從v出發(fā)的所有邊拓?fù)渑判蚺c強連通分量拓?fù)渑判蛲負(fù)渑判蚺c強連通分量67強連通分量Tarjan算法基于對圖深度優(yōu)先搜索的算法DFN（u）：u搜索到的次序編號（時間戳）Low（u）：u或者u的子樹能夠追溯到的最早的搜索棧中的節(jié)點的次序號。DFN(u)=Low(u)時，以u為根的搜索子樹上所有節(jié)點是一個強連通分量。拓?fù)渑判蚺c強連通分量強連通分量拓?fù)渑判蚺c強連通分量68拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量69拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量70拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量71拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量72拓?fù)渑判蚺c強連通分量拓?fù)渑判蚺c強連通分量73拓?fù)渑判蚺c強連通分量O（V+E）POJ2762拓?fù)渑判蚺c強連通分量O（V+E）74割點v：去掉點v后圖不連通橋/割邊e：去掉邊e后圖不連通雙連通分量：1、（邊）任意去掉一條邊，圖仍連通2、（點）任意去掉一個點，圖仍連通割點、橋、雙連通分量割點v：去掉點v后圖不連通割點、橋、雙連通分量75Tarjan算法求割點在圖的搜索樹中，如果u為割點，當(dāng)且僅當(dāng)滿足下面的條件：1、如果u為樹根，那么u必須有多于1棵子樹2、如果u不為樹根，那么（u,v）為樹枝邊，當(dāng)Low[v]>=DFN[u]時。割點、橋、雙聯(lián)通分量Tarjan算法求割點割點、橋、雙聯(lián)通分量76割點、橋、雙聯(lián)通分量割點、橋、雙聯(lián)通分量77在一個網(wǎng)絡(luò)中，某些點之間可以接發(fā)信息（單向）。問至少增加多少條邊可以使從任一點發(fā)送的信息可以到達(dá)其他所有點？

例題1在一個網(wǎng)絡(luò)中，某些點之間可以接發(fā)信息（單向）。問至少增