無向圖傳遞閉包

無向圖傳遞閉包第一頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

問題一、判斷無向圖中任意兩個(gè)頂點(diǎn)之間是否有路。例1、輸入一張無向圖，指出該圖中哪些頂點(diǎn)對(duì)之間有路。輸入：n（頂點(diǎn)數(shù)，1<=n<=20）；

e（邊數(shù)，1<=e<=210）；以下e行，每行為有邊連接的一對(duì)頂點(diǎn)。輸出：k行，每行兩個(gè)數(shù)，為存在路的頂點(diǎn)對(duì)序號(hào)i,j，要求i<j。

分析：

1、采用寬度優(yōu)先或深度優(yōu)先遍歷來解決。因?yàn)閺娜我庖粋€(gè)頂點(diǎn)出發(fā)，進(jìn)行一次遍歷，就可以求出此頂點(diǎn)和其它各個(gè)頂點(diǎn)的連通狀況。所以只要把每個(gè)頂點(diǎn)作為出發(fā)點(diǎn)都進(jìn)行一次遍歷，就能知道任意兩個(gè)頂點(diǎn)之間是否有路存在。一次遍歷的時(shí)間復(fù)雜度為O（n），要窮舉每個(gè)頂點(diǎn)，所以總的時(shí)間復(fù)雜度為O（n*n）。第二頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

2、設(shè)link,longlink:array[1..20,1..20]ofBoolean；分別存放無向圖和它的傳遞閉包。若longlink[i,j]=true，表示頂點(diǎn)對(duì)i,j之間有路；否則無路。我們采用遞推（迭代）的方法，不斷對(duì)longlink進(jìn)行運(yùn)算（產(chǎn)生longlink(0),longlink(1),……,longlink(n)）。對(duì)于i，j和k=1,……,n，如果圖中頂點(diǎn)i至頂點(diǎn)j間存在通路且通路上所有頂點(diǎn)的序號(hào)均屬于{1,2,……,k}，則定義longlinkij(k)=true；否則值為false。有：longlinkij(k)=longlinkij(k-1)or(longlinkik(k-1)andlonglinkkj(k-1))。計(jì)算過程如下：longlink的初值賦為link；fork:=1tondofori:=1tondoforj:=1tondolonglink[i,j]=longlink[i,j]or(longlink[i,k]andlonglink[k,j]);

由于布爾型的存儲(chǔ)量少于整數(shù)，且位邏輯運(yùn)算的執(zhí)行速度快于算術(shù)運(yùn)算，所以空間和時(shí)間效率都很好。時(shí)間復(fù)雜度為O（n*n*n）。了解Floyd算法求最短路徑問題的學(xué)生，一眼就應(yīng)該看出這個(gè)程序段和算法思想與Floyd算法是完全一致。第三頁，共二十二頁，2022年，8月28日varlink，longlink：array[1..20，1..20]ofboolean；{無向圖和無向圖的傳遞閉包。其中}我們遞推產(chǎn)生longlink(0)、longlink(1)、…longlink(n)。在遞推過程中，路徑長(zhǎng)度的’+’運(yùn)算和比較大小的運(yùn)算用相應(yīng)的邏輯運(yùn)算符’and’和’or’代替。對(duì)于i，j和k=1‥n，如果圖中結(jié)點(diǎn)i至結(jié)點(diǎn)j間存在通路且通路上所有結(jié)點(diǎn)的序號(hào)均屬于{1‥k}，則定義longlinkij(k)=1；否則longlinkij(k)=0。longlinkij(k)=longlinkij(k-1)or(longlinkik(k-1)andlonglinkkj(k-1))傳遞閉包longlink的計(jì)算過程如下：longlink←link；fork←1tondo{枚舉中間頂點(diǎn)}fori←1tondo{枚舉所有頂點(diǎn)對(duì)}forj←1tondo{計(jì)算頂點(diǎn)i和頂點(diǎn)j的連通情況}longlink[i，j]←longlink[i，j]or(longlink[i，k]andlonglink[k，j])；第四頁，共二十二頁，2022年，8月28日主程序fillchar(longlink，sizeof(longlink)，0)；{傳遞閉包初始化}fillchar(link，sizeof(link)，0)；{無向圖初始化}readln(n)；readln(e)；{讀頂點(diǎn)數(shù)和邊數(shù)}fork←1toedo{輸入無向圖的信息}beginreadln(i，j)；link[i，j]←true；link[j，i]←true；

end；{for}計(jì)算傳遞閉包longlink；fori←1ton-1do{輸出所有存在通路的頂點(diǎn)對(duì)}forj←i+1tondoiflonglink[i，j]then輸出i和j；第五頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

問題二、尋找滿足條件的連通分支。例2、輸入一張頂點(diǎn)帶權(quán)的無向圖，分別計(jì)算含頂點(diǎn)數(shù)最多的一個(gè)連通分支和頂點(diǎn)的權(quán)之和最大的一個(gè)連通分支。輸入：n（頂點(diǎn)數(shù)，1<=n<=20）；以下n行，依次表示頂點(diǎn)1~頂點(diǎn)n上的權(quán)；

e（邊數(shù)，1<=e<=210）；以下e行，每行為有邊連接的一對(duì)頂點(diǎn)。輸出：兩行，一行為含頂點(diǎn)數(shù)最多的一個(gè)連通分支，一行為頂點(diǎn)的權(quán)之和最大的一個(gè)連通分支，輸出時(shí)按頂點(diǎn)編號(hào)從小到大輸出。

第六頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

[問題分析]

我們可以先通過例1的longlink，計(jì)算出每個(gè)頂點(diǎn)所在的連通分支，然后在所有可能的連通分支中找出滿足條件的解即可。至于計(jì)算連通分支的頂點(diǎn)方案，只要分別從連通分支中任選一個(gè)代表頂點(diǎn)，由此出發(fā)，通過深度優(yōu)先搜索即可得到頂點(diǎn)方案。設(shè)：best,besti分別存放含頂點(diǎn)數(shù)最多的連通分支中的頂點(diǎn)數(shù)和代表頂點(diǎn)；max,maxk分別存放頂點(diǎn)的權(quán)之和最大的連通分支的頂點(diǎn)權(quán)之和和代表頂點(diǎn)；計(jì)算best,besti,max,maxk的過程如下：

1、讀入無向圖的信息；

2、計(jì)算傳遞閉包longlink；

第七頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

[問題分析]3、窮舉每一個(gè)頂點(diǎn)

forI:=1tondobegink:=0;s:=0forj:=1tondo{計(jì)算頂點(diǎn)i所在連通分支中的頂點(diǎn)總數(shù)k和頂點(diǎn)的權(quán)之和s}iflonglink[i,j]thenbegininc(k);inc(s,頂點(diǎn)j的權(quán))end;ifk>bestthenbeginbest:=k;besti:=Iend;{若k為目前最大，則記入best,i作為代表頂點(diǎn)記入besti}ifs>maxthenbeginmax:=s;maxk:=Iend;{若s為目前最大，則記入max,i作為代表頂點(diǎn)記入maxk}ifk=nthenbreak;{若整個(gè)圖是連通圖，則退出}end;第八頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

[問題分析]4、dfs(besti);{從代表頂點(diǎn)besti出發(fā)，深度優(yōu)先搜索含頂點(diǎn)數(shù)最多的連通分支}5、dfs(maxk);{從代表頂點(diǎn)maxk出發(fā)，深度優(yōu)先搜索頂點(diǎn)的權(quán)之和最大的連通分支}

顯然，以上算法的時(shí)間復(fù)雜度為O（n*n）。

第九頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

三、歐拉回路

1、歐拉路：在無孤立頂點(diǎn)的圖中，若存在一條路，經(jīng)過圖中每條邊一次且僅一次，則稱此路為歐拉路。如左圖中存在一條從頂點(diǎn)1到頂點(diǎn)6的歐拉路。后面的例題（一筆畫問題）本質(zhì)上就是判斷一個(gè)圖是否存在歐拉路。2、歐拉回路：在無孤立頂點(diǎn)的圖中，若存在一條路，經(jīng)過圖中每條邊一次且僅一次，且回到原來位置，則稱此路為歐拉回路。如右圖中任意兩個(gè)頂點(diǎn)之間都存在歐拉回路。著名的柯尼斯堡七橋問題（圖論起源），本質(zhì)上就是討論一個(gè)圖的歐拉回路問題。

3、歐拉圖：存在歐拉回路的圖，稱為歐拉圖，右圖所示的圖就是一個(gè)歐拉圖。第十頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

三、歐拉回路

4、定理1：存在歐拉路的條件：圖是連通的，且存在0個(gè)或2個(gè)奇點(diǎn)。如果存在2個(gè)奇點(diǎn)，則歐拉路一定是從一個(gè)奇點(diǎn)出發(fā)，以另一個(gè)奇點(diǎn)結(jié)束。5、定理2：存在歐拉回路的條件：圖是連通的，且不存在奇點(diǎn)。6、哈密爾頓圖：在無孤立頂點(diǎn)的連通圖中，若存在一條路，經(jīng)過圖中每個(gè)頂點(diǎn)一次且僅一次，則稱此圖為哈密爾頓圖。

7、哈密爾頓環(huán)：是一條沿著圖的n條邊環(huán)行的路徑，它訪問每一個(gè)頂點(diǎn)一次且僅一次，并且返回到它的開始位置。

第十一頁，共二十二頁，2022年，8月28日（3）計(jì)算每一對(duì)頂點(diǎn)間的最短路徑（floyd算法）

現(xiàn)有一張城市地圖，圖中的頂點(diǎn)為城市，有向邊代表兩個(gè)城市間的連通關(guān)系，邊上的權(quán)即為距離?，F(xiàn)在的問題是，為每一對(duì)可達(dá)的城市間設(shè)計(jì)一條公共汽車線路，要求線路的長(zhǎng)度在所有可能的方案里是最短的。輸入：

n(城市數(shù)，1≤n≤20)e(有向邊數(shù)1≤e≤210)

以下e行，每行為邊（i,j）和該邊的距離wij（1≤i,j≤n）輸出：

k行，每行為一條公共汽車線路第十二頁，共二十二頁，2022年，8月28日在枚舉途徑某中間頂點(diǎn)k的任兩個(gè)頂點(diǎn)對(duì)i和j時(shí)，將頂點(diǎn)i和頂點(diǎn)j中間加入頂點(diǎn)k后是否連通的判斷，改為頂點(diǎn)i途徑頂點(diǎn)k至頂點(diǎn)j的路徑是否為頂點(diǎn)i至頂點(diǎn)j的最短路徑（1≤i，j，k≤n）。顯然三重循環(huán)即可計(jì)算出任一對(duì)頂點(diǎn)間的最短路徑。設(shè)n—有向圖的結(jié)點(diǎn)個(gè)數(shù)；path—最短路徑集合。其中path[i，j]為vi至vj的最短路上vj的前趨結(jié)點(diǎn)序號(hào)(1≤i，j≤n)；adj—最短路徑矩陣。初始時(shí)為有向圖的相鄰矩陣用類似傳遞閉包的計(jì)算方法反復(fù)對(duì)adj矩陣進(jìn)行運(yùn)算，最后使得adj成為存儲(chǔ)每一對(duì)頂點(diǎn)間的最短路徑的矩陣第十三頁，共二十二頁，2022年，8月28日Varadj：array[1‥n，1‥n]ofreal；path：array[1‥n，1‥n]of0‥n；計(jì)算每一對(duì)頂點(diǎn)間最短路徑的方法如下：adj矩陣的每一個(gè)元素初始化為∞；fori←1tondo{初始時(shí)adj為有向圖的相鄰矩陣，path存儲(chǔ)邊信息}forj←1tondoifwij<>0thenbeginadj[i，j]←wij；path[i，j]←i；end{then}elsepath[i，j]←0；fork←1tondo{枚舉每一個(gè)中間頂點(diǎn)}fori←1tondo{枚舉每一個(gè)頂點(diǎn)對(duì)}forj←1tondoifadj[i，k]+adj[k，j]<adj[i，j]{若vi經(jīng)由vk至vj的路徑目前最優(yōu)，則記下}thenbeginadj[i，j]←adj[i，k]+adj[k，j]；path[i，j]←path[k，j]；end，{then}第十四頁，共二十二頁，2022年，8月28日由矩陣path可推知任一結(jié)點(diǎn)對(duì)i、j之間的最短路徑方案Procedureprint(i，j)；beginifi=jthen輸出ielseififpath[i，j]=0then輸出結(jié)點(diǎn)i與結(jié)點(diǎn)j之間不存在通路elsebeginprint(i，path[i，j])；{遞歸i頂點(diǎn)至j頂點(diǎn)的前趨頂點(diǎn)間的最短路徑}輸出j；end；{else}end；{print}由此得出主程序距離矩陣w初始化為0；輸入城市地圖信息（頂點(diǎn)數(shù)、邊數(shù)和距離矩陣w）；計(jì)算每一對(duì)頂點(diǎn)間最短路徑的矩陣path；fori←1tondo{枚舉每一個(gè)頂點(diǎn)對(duì)}forj←1tondoifpath[i，j]<>0{若頂點(diǎn)i可達(dá)頂點(diǎn)j，則輸出最短路徑方案}thenbeginprint（i，j）；writeln；end；{then}

第十五頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

三、歐拉回路

8、尋找歐拉回路的算法

尋找歐拉回路的算法有多種，下面介紹一種基于遞歸的經(jīng)典算法框架：find_circuit(結(jié)點(diǎn)i)；{當(dāng)結(jié)點(diǎn)i有鄰居時(shí)

{選擇任意一個(gè)鄰居j；刪除邊(i,j)；

find_circuit（結(jié)點(diǎn)j）；

}circuit[circuitpos]:=結(jié)點(diǎn)i；

circuitpos:=circuitpos+1；}

如果尋找歐拉回路，對(duì)任意一個(gè)點(diǎn)執(zhí)行find_circuit；如果是尋找歐拉路徑，對(duì)一個(gè)奇點(diǎn)執(zhí)行find_circuit；算法的時(shí)間復(fù)雜度為O(m+n)。第十六頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

三、歐拉回路

9、尋找哈密爾頓環(huán)的算法到現(xiàn)在為止，尋找哈密爾頓環(huán)并沒有一種有效的算法，一般只能用搜索解決。第十七頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

四、應(yīng)用舉例（作業(yè)）例4、一筆畫問題（one.???）[問題描述]

編程對(duì)給定的一個(gè)圖，判斷能否一筆畫出，若能請(qǐng)輸出一筆畫的先后順序，否則輸出“NoSolution！”。[輸入格式]

輸入文件共n+1行，第1行為圖的頂點(diǎn)數(shù)n，接下來的n行（每行n個(gè)數(shù)據(jù)）為圖的鄰接矩陣，

G[i,j]=1表示頂點(diǎn)i和頂點(diǎn)j有邊相連，G[i,j]=0表示頂點(diǎn)i和頂點(diǎn)j無邊相連。

[輸出格式]

若能一筆畫出，則輸出一筆畫出的頂點(diǎn)先后順序，否則輸出“NoSolution！”。

[樣例輸入]6010011101101010100011011100101110110[樣例輸出]5--->1--->2--->3--->4--->2--->6--->4--->5--->6--->1

第十八頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

例5、鏟雪（snow.???）隨著白天越來越短夜晚越來越長(zhǎng)，我們不得不考慮鏟雪問題了。整個(gè)城市所有的道路都是雙車道，因?yàn)槌鞘蓄A(yù)算的削減，整個(gè)城市只有1輛鏟雪車。鏟雪車只能把它開過的地方（車道）的雪鏟干凈，無論哪兒有雪，鏟雪車都得從停放的地方出發(fā)，游歷整個(gè)城市的街道。現(xiàn)在的問題是：最少要花多少時(shí)間去鏟掉所有道路上的雪呢？

輸入：輸入數(shù)據(jù)的第1行表示鏟雪車的停放坐標(biāo)（x,y），x，y為整數(shù)，單位為米。下面最多有100行，每行給出了一條街道的起點(diǎn)坐標(biāo)和終點(diǎn)坐標(biāo)，所有街道都是筆直的，且都是雙向一個(gè)車道。鏟雪車可以在任意交叉口、或任何街道的末尾任意轉(zhuǎn)向，包括轉(zhuǎn)U型彎。鏟雪車鏟雪時(shí)前進(jìn)速度為20km/h，不鏟雪時(shí)前進(jìn)速度為50km/h。保證：鏟雪車從起點(diǎn)一定可以到達(dá)任何街道。輸出：鏟掉所有街道上的雪并且返回出發(fā)點(diǎn)的最短時(shí)間，精確到分種。輸入樣例：

000010000100005000-100005000100005000100001000010000

輸出樣例：

3:55

{注解：3小時(shí)55分鐘。}第十九頁，共二十二頁，2022年，8月28日無向圖的傳遞閉包

例6、房間問題（castle.???)

一座城堡被分成ｍ*ｎ個(gè)方塊（m≤50，n≤50），每個(gè)方塊可有0～4堵墻（0表示無墻）。下面展示出了建筑平面圖，圖中的加粗黑線代表墻。幾個(gè)連通的方塊組成房間，房間與房間之間一定是用黑線（墻）隔開的。