資源描述：
《圖的連通性問題.ppt》由會員上傳分享，免費在線閱讀，更多相關內容在教育資源-天天文庫。
1、圖的連通性問題內容概要并查集割點和橋強連通分量TarjanKosaraju1.并查集并查集是一種用來管理元素分組的數據結構并查集使用樹形結構進行存儲并查集具有兩個操作:查詢元素a和元素b是否屬于同一個分組合并元素a和元素b所在的分組注意:并查集雖然能夠進行合并操作,但卻無法進行分割操作1.并查集15234a.初始化1.并查集12211b.合并32456132456樣例1樣例21.并查集c.查詢1324563256的根是的根是141.并查集d.代碼實現1.并查集1.并查集1.并查集1.并查集e.問題132561
2、43256141.并查集f.優(yōu)化11.并查集e.問題2132456132456132456方式1方式21.并查集f.優(yōu)化2對于問題2,我們可以記錄每個樹的高度合并時,如果兩棵樹的高度不同那么我們將高度低的樹合并到高度高的樹1.并查集g.優(yōu)化后的代碼1.并查集1.并查集2.割點和橋割點:在無向聯(lián)通圖G=(V,E)中,如果刪除一個點u及其相關的邊,會使得新的圖不連通,那么點u就稱為圖G的一個割點橋(割邊):在無向聯(lián)通圖G=(V,E)中,如果刪除一條邊e=(u,v)后,會使得新的圖不連通,那么邊e=(u,v)就稱為
3、圖G的橋,又稱為割邊a.概念2.割點和橋b.性質一個無向連通圖,如果沒有割點,那么任意兩點之間,都存在點集互不相交(除了起點與終點外)的兩條路徑一個無向連通圖,如果沒有橋,那么任意兩點之間,都存在邊集互不相交的兩條路徑2.割點和橋45613251342圖1圖22.割點和橋問題:那么我們該如何求解割點(橋)呢？嘗試刪除每個節(jié)點(邊)，然后用DFS判斷連通分量是否增加深入挖掘DFS的性質，在線性時間(即O(V+E)時間)內求解所有的割點(橋)時間復雜度O(V(V+E))2.割點和橋c.DFS樹ACBDFEAEBD
4、FC(1,12)(2,11)(3,10)(4,7)(5,6)(8,9)圖1圖2黑色的邊稱為樹邊對圖1進行DFS就能得到圖2(不唯一)，圖2就稱為圖1的DFS樹，又稱為深搜樹每個節(jié)點都有一對數字(x,y)x表示第一次訪問該點的次序y表示第二次訪問該點的次序紅色的箭頭稱為返祖邊(或者叫反向邊)2.割點和橋在無向連通圖G的DFS樹中，非根節(jié)點u是G的割點當且僅當u存在一個子節(jié)點v，使得v及其后代都沒有反向邊連回u的祖先(不含u)。d.定理2.割點和橋證明：ufvufv圖1圖2如圖，考慮u的任意子結點v。如果v及其后
5、代不能連回f，則刪除u之后，f和v不在聯(lián)通；反之，如果v或者它的某一個后代存在一條反向邊連回f，則刪除u之后，以v根的整棵子樹中的所有結點都可以利用這條反向邊與f連通。如果所有子樹中的結點都和f連通，根據“連通”關系的傳遞性，整個圖就是連通的。2.割點和橋f.實現為了方向起見，pre[u]為u在DFS樹的先序遍歷的順序，low[u]為結點u及其后代所能連回的最早祖先的pre值。當節(jié)點u存在一個子結點v，使得low[v]≥pre[u]，那么結點u就為割點。另外，不難發(fā)現當low[v]>pre[u]時，那么e=(
6、u,v)即為橋(割邊)。于是我們可以將定理寫成：{min(low[u],low[v])(u,v)為樹邊min(low[u],pre[v])(u,v)為返祖邊且v不是u的父節(jié)點2.割點和橋g.代碼(以割點為例)2.割點和橋2.割點和橋3.強連通分量a.概念一個有向圖G=(V,E)被稱為強連通圖，當且僅當圖中任意兩點間都存在一條路徑。即對于圖中任意兩點u和v，存在u到v的路徑和v到u的路徑。強連通分量(StronglyConnectedComponent,SCC)是指一個有向圖G的一個極大強連通子圖。b.性質一個
7、有向環(huán)是最簡單的強連通圖。如果一個有向圖G的所有強連通分量都只有一個點，那么這個圖是有向無環(huán)圖，即存在拓撲序。3.強連通分量c.強連通分量分解任意的有向圖都可以分解成若干不相交的強連通分量，這就是強連通分量分解。把分解之后的強連通分量縮成一個頂點，我們就得到了一個DAG(有向無環(huán)圖)。1574328612,3,485,6,71574328612,3,485,6,7問題：我們應該如果求解有向圖的各個強連通分量呢？我們再次借助DFS，如圖，如果我們從8開始DFS，將得到只包含{8}的一棵DFS樹;從5出發(fā)，得到{
8、5,6,7};再從2出發(fā)，得到{2,3,4};從1出發(fā)，得到{1}。可以發(fā)現我們“輕而易舉”的就得到了SCC。細心的同學會發(fā)現，這種方式與遍歷的順序有著極大的關系。3.強連通分量Kosaraju算法第二次DFS時，先將所有邊反向，然后從標號最大的頂點為起點就行DFS。這樣每次DFS所遍歷的頂點集合就構成了一個強連通分量。對于其他剩余的未訪問的頂點，不斷重復以上過程。該算法只進行了兩次DFS，故時間復
