圖的連通性問(wèn)題.ppt

《圖的連通性問(wèn)題.ppt》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、圖的連通性問(wèn)題內(nèi)容概要并查集割點(diǎn)和橋強(qiáng)連通分量TarjanKosaraju1.并查集并查集是一種用來(lái)管理元素分組的數(shù)據(jù)結(jié)構(gòu)并查集使用樹形結(jié)構(gòu)進(jìn)行存儲(chǔ)并查集具有兩個(gè)操作:查詢?cè)豠和元素b是否屬于同一個(gè)分組合并元素a和元素b所在的分組注意:并查集雖然能夠進(jìn)行合并操作,但卻無(wú)法進(jìn)行分割操作1.并查集15234a.初始化1.并查集12211b.合并32456132456樣例1樣例21.并查集c.查詢1324563256的根是的根是141.并查集d.代碼實(shí)現(xiàn)1.并查集1.并查集1.并查集1.并查集e.問(wèn)題132561

2、43256141.并查集f.優(yōu)化11.并查集e.問(wèn)題2132456132456132456方式1方式21.并查集f.優(yōu)化2對(duì)于問(wèn)題2,我們可以記錄每個(gè)樹的高度合并時(shí),如果兩棵樹的高度不同那么我們將高度低的樹合并到高度高的樹1.并查集g.優(yōu)化后的代碼1.并查集1.并查集2.割點(diǎn)和橋割點(diǎn):在無(wú)向聯(lián)通圖G=(V,E)中,如果刪除一個(gè)點(diǎn)u及其相關(guān)的邊,會(huì)使得新的圖不連通,那么點(diǎn)u就稱為圖G的一個(gè)割點(diǎn)橋(割邊):在無(wú)向聯(lián)通圖G=(V,E)中,如果刪除一條邊e=(u,v)后,會(huì)使得新的圖不連通,那么邊e=(u,v)就稱為

3、圖G的橋,又稱為割邊a.概念2.割點(diǎn)和橋b.性質(zhì)一個(gè)無(wú)向連通圖,如果沒(méi)有割點(diǎn),那么任意兩點(diǎn)之間,都存在點(diǎn)集互不相交(除了起點(diǎn)與終點(diǎn)外)的兩條路徑一個(gè)無(wú)向連通圖,如果沒(méi)有橋,那么任意兩點(diǎn)之間,都存在邊集互不相交的兩條路徑2.割點(diǎn)和橋45613251342圖1圖22.割點(diǎn)和橋問(wèn)題:那么我們?cè)撊绾吻蠼飧铧c(diǎn)(橋)呢？嘗試刪除每個(gè)節(jié)點(diǎn)(邊)，然后用DFS判斷連通分量是否增加深入挖掘DFS的性質(zhì)，在線性時(shí)間(即O(V+E)時(shí)間)內(nèi)求解所有的割點(diǎn)(橋)時(shí)間復(fù)雜度O(V(V+E))2.割點(diǎn)和橋c.DFS樹ACBDFEAEBD

4、FC(1,12)(2,11)(3,10)(4,7)(5,6)(8,9)圖1圖2黑色的邊稱為樹邊對(duì)圖1進(jìn)行DFS就能得到圖2(不唯一)，圖2就稱為圖1的DFS樹，又稱為深搜樹每個(gè)節(jié)點(diǎn)都有一對(duì)數(shù)字(x,y)x表示第一次訪問(wèn)該點(diǎn)的次序y表示第二次訪問(wèn)該點(diǎn)的次序紅色的箭頭稱為返祖邊(或者叫反向邊)2.割點(diǎn)和橋在無(wú)向連通圖G的DFS樹中，非根節(jié)點(diǎn)u是G的割點(diǎn)當(dāng)且僅當(dāng)u存在一個(gè)子節(jié)點(diǎn)v，使得v及其后代都沒(méi)有反向邊連回u的祖先(不含u)。d.定理2.割點(diǎn)和橋證明：ufvufv圖1圖2如圖，考慮u的任意子結(jié)點(diǎn)v。如果v及其后

5、代不能連回f，則刪除u之后，f和v不在聯(lián)通；反之，如果v或者它的某一個(gè)后代存在一條反向邊連回f，則刪除u之后，以v根的整棵子樹中的所有結(jié)點(diǎn)都可以利用這條反向邊與f連通。如果所有子樹中的結(jié)點(diǎn)都和f連通，根據(jù)“連通”關(guān)系的傳遞性，整個(gè)圖就是連通的。2.割點(diǎn)和橋f.實(shí)現(xiàn)為了方向起見，pre[u]為u在DFS樹的先序遍歷的順序，low[u]為結(jié)點(diǎn)u及其后代所能連回的最早祖先的pre值。當(dāng)節(jié)點(diǎn)u存在一個(gè)子結(jié)點(diǎn)v，使得low[v]≥pre[u]，那么結(jié)點(diǎn)u就為割點(diǎn)。另外，不難發(fā)現(xiàn)當(dāng)low[v]>pre[u]時(shí)，那么e=(

6、u,v)即為橋(割邊)。于是我們可以將定理寫成：{min(low[u],low[v])(u,v)為樹邊min(low[u],pre[v])(u,v)為返祖邊且v不是u的父節(jié)點(diǎn)2.割點(diǎn)和橋g.代碼(以割點(diǎn)為例)2.割點(diǎn)和橋2.割點(diǎn)和橋3.強(qiáng)連通分量a.概念一個(gè)有向圖G=(V,E)被稱為強(qiáng)連通圖，當(dāng)且僅當(dāng)圖中任意兩點(diǎn)間都存在一條路徑。即對(duì)于圖中任意兩點(diǎn)u和v，存在u到v的路徑和v到u的路徑。強(qiáng)連通分量(StronglyConnectedComponent,SCC)是指一個(gè)有向圖G的一個(gè)極大強(qiáng)連通子圖。b.性質(zhì)一個(gè)

7、有向環(huán)是最簡(jiǎn)單的強(qiáng)連通圖。如果一個(gè)有向圖G的所有強(qiáng)連通分量都只有一個(gè)點(diǎn)，那么這個(gè)圖是有向無(wú)環(huán)圖，即存在拓?fù)湫颉?.強(qiáng)連通分量c.強(qiáng)連通分量分解任意的有向圖都可以分解成若干不相交的強(qiáng)連通分量，這就是強(qiáng)連通分量分解。把分解之后的強(qiáng)連通分量縮成一個(gè)頂點(diǎn)，我們就得到了一個(gè)DAG(有向無(wú)環(huán)圖)。1574328612,3,485,6,71574328612,3,485,6,7問(wèn)題：我們應(yīng)該如果求解有向圖的各個(gè)強(qiáng)連通分量呢？我們?cè)俅谓柚鶧FS，如圖，如果我們從8開始DFS，將得到只包含{8}的一棵DFS樹;從5出發(fā)，得到{

8、5,6,7};再?gòu)?出發(fā)，得到{2,3,4};從1出發(fā)，得到{1}?？梢园l(fā)現(xiàn)我們“輕而易舉”的就得到了SCC。細(xì)心的同學(xué)會(huì)發(fā)現(xiàn)，這種方式與遍歷的順序有著極大的關(guān)系。3.強(qiáng)連通分量Kosaraju算法第二次DFS時(shí)，先將所有邊反向，然后從標(biāo)號(hào)最大的頂點(diǎn)為起點(diǎn)就行DFS。這樣每次DFS所遍歷的頂點(diǎn)集合就構(gòu)成了一個(gè)強(qiáng)連通分量。對(duì)于其他剩余的未訪問(wèn)的頂點(diǎn)，不斷重復(fù)以上過(guò)程。該算法只進(jìn)行了兩次DFS，故時(shí)間復(fù)