圖的搜索算法

圖的搜索算法第一頁(yè)，共三十九頁(yè)，編輯于2023年，星期二圖的鄰接表表示對(duì)圖（有向或無(wú)向）G=<V,E>（為方便記，假定V={1,2,…,n}），其鄰接表表示是一個(gè)由|V|個(gè)鏈表組成數(shù)組，對(duì)每個(gè)u

V，鏈表Adj[u]稱(chēng)為對(duì)應(yīng)頂點(diǎn)u的鄰接表。它包含G中所有與u相鄰的頂點(diǎn)。每個(gè)鄰接表中頂點(diǎn)通常是按任意順序存放的。第二頁(yè)，共三十九頁(yè)，編輯于2023年，星期二6.1廣度優(yōu)先搜索1．問(wèn)題的理解與描述給定一個(gè)圖（有向或無(wú)向）G=<V,E>和其中的一個(gè)源頂點(diǎn)s，廣度優(yōu)先搜索系統(tǒng)地探索G的邊以“發(fā)現(xiàn)”從s出發(fā)每一個(gè)可達(dá)的頂點(diǎn)：發(fā)現(xiàn)從s出發(fā)距離為k+1的頂點(diǎn)之前先發(fā)現(xiàn)距離為k的頂點(diǎn)。搜索所經(jīng)路徑中的頂點(diǎn)，按先后順序構(gòu)成“父子關(guān)系”：先發(fā)現(xiàn)的頂點(diǎn)u，并由u出發(fā)發(fā)現(xiàn)與其相鄰的頂點(diǎn)v，則稱(chēng)u為v的父親。由于每個(gè)頂點(diǎn)只有最多一個(gè)頂點(diǎn)作為它的父親，所以搜索路徑必構(gòu)成一棵根樹(shù)（樹(shù)根為起始頂點(diǎn)s）G。我們把這棵樹(shù)稱(chēng)為G的廣度優(yōu)先樹(shù)。與此同時(shí)，我們還計(jì)算出了從s到這些可達(dá)頂點(diǎn)的距離（最少的邊數(shù)即“最短路徑”）。這樣，圖的廣度搜索問(wèn)題形式化表述如下。輸入：圖G=<V,E>，源頂點(diǎn)sV。輸出：G的廣度優(yōu)先樹(shù)G以及樹(shù)中從樹(shù)根s（源頂點(diǎn)）到各節(jié)點(diǎn)的距離。第三頁(yè)，共三十九頁(yè)，編輯于2023年，星期二對(duì)一個(gè)無(wú)向圖的BFS操作第四頁(yè)，共三十九頁(yè)，編輯于2023年，星期二2．算法的偽代碼描述BFS(G,s)1for

每個(gè)頂點(diǎn)uV[G]-{s}2do

color[u]←WHITE3d[u]←4 [u]←NIL5color[s]←GRAY6d[s]←07Q←?8ENQUEUE(Q,s)9while

Q≠?10do

u←DEQUEUE(Q)11foreachv

Adj[u]12doif

color[v]=WHITE13then

color[v]←GRAY14 [v]←u15d[v]←d[u]+116ENQUEUE(Q,v)17 color[u]←BLACK18return

andd第五頁(yè)，共三十九頁(yè)，編輯于2023年，星期二3．算法的正確性引理6-1從源頂點(diǎn)s到任何頂點(diǎn)v的距離必不超過(guò)運(yùn)行BFS后過(guò)此頂點(diǎn)的d屬性。引理6-2設(shè)隊(duì)列Q={v1,v2,…,vr}。則d[vr]d[v1]+1（即對(duì)尾元素的d屬性不超過(guò)隊(duì)首元素的d屬性加1），且d[v1]d[v2]...d[vr]。定理6-3運(yùn)行BFS后，圖G中各頂點(diǎn)v的d屬性記錄了s到v的距離。第六頁(yè)，共三十九頁(yè)，編輯于2023年，星期二4．算法的運(yùn)行時(shí)間第1～4行的循環(huán)重復(fù)|V|次。另一方面，由于每條邊在搜索過(guò)程中有且僅有一次被訪問(wèn)，第9～17行兩重循環(huán)嵌套內(nèi)的操作被執(zhí)行|E|次。所以BFS的總運(yùn)行時(shí)間是Θ(V+E)。于是，廣度優(yōu)先搜索運(yùn)行于G的鄰接表示規(guī)模的線性時(shí)間內(nèi)。第七頁(yè)，共三十九頁(yè)，編輯于2023年，星期二6.2深度優(yōu)先搜索深度優(yōu)先搜索（DepthFirstSearch，DFS）所遵循的策略，如同其名稱(chēng)所云，是在圖中盡可能“更深”地進(jìn)行搜索。在深度優(yōu)先搜索中，對(duì)最新發(fā)現(xiàn)的頂點(diǎn)v若此頂點(diǎn)尚有未探索過(guò)從其出發(fā)的邊就探索之。當(dāng)v的所有邊都被探索過(guò)，搜索“回溯”到從其出發(fā)發(fā)現(xiàn)頂點(diǎn)v的頂點(diǎn)。此過(guò)程繼續(xù)直至發(fā)現(xiàn)所有從源點(diǎn)可達(dá)的頂點(diǎn)。若圖中還有未發(fā)現(xiàn)的頂點(diǎn)，則以其中之一為新的源點(diǎn)重復(fù)搜索，直至所有的頂點(diǎn)都被發(fā)現(xiàn)。與BFS中源頂點(diǎn)是指定的稍有不同。DFS搜索軌跡G將形成一片森林——深度優(yōu)先森林第八頁(yè)，共三十九頁(yè)，編輯于2023年，星期二1．問(wèn)題的理解與描述在深度優(yōu)先搜索過(guò)程中對(duì)每一個(gè)頂點(diǎn)u跟蹤兩個(gè)時(shí)間：發(fā)現(xiàn)時(shí)間d[u]和完成時(shí)間f[u]。d[u]記錄首次發(fā)現(xiàn)（u由白色變成灰色）時(shí)刻，f[u]記錄完成v的鄰接表檢測(cè)（變成黑色）時(shí)刻。輸入：圖G=<V,E>。輸出：G的深度優(yōu)先森林G以及圖中各頂點(diǎn)在搜索過(guò)程中的發(fā)現(xiàn)時(shí)間和完成時(shí)間。第九頁(yè)，共三十九頁(yè)，編輯于2023年，星期二2．算法的偽代碼描述DFS(G)1foreachvertexuV[G]2do

color[u]←WHITE3[u]←NIL4time←05S←6foreachvertexs

V[G]7doif

color[s]=WHITE8 thencolor[s]←GRAY9 d[s]←time←time+110 PUSH(S,s)11 while

S≠

12 dou←TOP(S)13 ifvAdj[u]andcolor[v]=WHITE14 thencolor[v]←GRAY15 [v]←u16 d[v]←time←time+117 PUSH(S,v)18 elsecolor[u]←BLACK19 f[u]←time←time+120 POP(S)21return

d,f,and第十頁(yè)，共三十九頁(yè)，編輯于2023年，星期二DFS施于一個(gè)有向圖的過(guò)程第十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期二3．算法的運(yùn)行時(shí)間DFS的運(yùn)行時(shí)間如何？第1～2行的循環(huán)Θ(V)。內(nèi)嵌于第14～20行操作對(duì)G的每條邊執(zhí)行一次，因此耗時(shí)所以DFS的運(yùn)行時(shí)間為Θ(V+E)。第十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期二6.2.3有向無(wú)圈圖的拓?fù)渑判駾FS算法可以修改成能對(duì)各條邊在遇到它們時(shí)進(jìn)行分類(lèi)。關(guān)鍵的思想是，每一條邊(u,v)在首次被探索時(shí)可以根據(jù)頂點(diǎn)v的顏色來(lái)分類(lèi)（但是進(jìn)邊和跨邊不能區(qū)分）：白色（WHITE）意味著一條樹(shù)枝邊；灰色（GRAY）意味著一條回邊；黑色（BLACK）意味著一條進(jìn)邊或跨邊。圖G是無(wú)圈的充分必要條件是G的一次深度優(yōu)先搜索不產(chǎn)生回邊。第十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期二問(wèn)題的理解與描述一個(gè)有向無(wú)圈圖G=<V,E>（DAG）的拓?fù)渑判蚴瞧渌许旤c(diǎn)的一個(gè)線性排列，使得若邊(u,v)包含在G中，則u在排列中必出現(xiàn)在v前（若圖不是無(wú)圈的，則不可能有此線性排列）。一個(gè)圖的拓?fù)渑判蚩杀灰暈閷D的所有頂點(diǎn)水平排列時(shí)，所有的有向邊從左指向右。輸入：有向圖G。輸出：若G是DAG，輸出G的各頂點(diǎn)的一個(gè)拓?fù)渑判颍駝t輸出出錯(cuò)信息。第十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期二算法的偽代碼描述TOPLOGICAL-SORT(G)1foreachvertexuV[G]2do

color[u]←WHITE3acyclicity←true4top-logic←S←5foreachvertexs

V[G]6doif

color[s]=WHITE7 then

color[s]←GRAY8 PUSH(S,s)9 while

S≠

10 dou←TOP(S)11 ifvAdj[u]andcolor[v]=GRAY12 then

acyclicity←false13 ifvAdj[u]andcolor[v]=WHITE14 thencolor[v]←GRAY15 PUSH(S,v)16 else

color[u]←BLACK17 PUSH(top-logic,u)18 POP(S)19ifacyclicity=true20 then

return

top-logic21 elseprint"GisnotaDAG!“由于TOPLOGICAL-SORT的運(yùn)行時(shí)間與DFS的運(yùn)行時(shí)間一致，所以，可以在時(shí)間Θ(V+E)內(nèi)計(jì)算有向無(wú)圈圖G=<V,E>的拓?fù)渑判颉５谑屙?yè)，共三十九頁(yè)，編輯于2023年，星期二6.3有向圖的強(qiáng)連通分支有向圖G=(V,E)的一個(gè)強(qiáng)連通分支C

V是一個(gè)使得其中每一對(duì)頂點(diǎn)u和v均有uv及vu，即頂點(diǎn)u和v是相互可達(dá)且對(duì)任意wV-C，C{w}中至少有一對(duì)頂點(diǎn)不能相互可達(dá)的頂點(diǎn)集合。把一個(gè)有向圖G中的各個(gè)強(qiáng)連通分支收縮為一個(gè)“頂點(diǎn)”，則將得到一個(gè)稱(chēng)為G的分支圖的有向圖。第十六頁(yè)，共三十九頁(yè)，編輯于2023年，星期二定理6-4有向圖的分支圖是一個(gè)有向無(wú)圈圖。對(duì)G的分支圖中的各個(gè)頂點(diǎn)（G的各個(gè)強(qiáng)連通分支Ci，i=1,2,…,k）定義發(fā)現(xiàn)時(shí)間和完成時(shí)間d(Ci)=minuCi

{d[u]}及f(Ci)=maxuCi

{f[u]}。第十七頁(yè)，共三十九頁(yè)，編輯于2023年，星期二1．問(wèn)題的理解與描述計(jì)算強(qiáng)連通分支的問(wèn)題形式化表示為：輸入：有向圖G。輸出：G的各強(qiáng)連通分支{C1,C2,…,Ck}。引理6-5設(shè)C和C′是有向圖G=(V,E)的兩個(gè)不同的強(qiáng)連通分支。在一次深度優(yōu)先搜索中其完成時(shí)間分別為f(C)和f(C′)。若有邊(u,v)

ET，其中u

C及v

C′。則f(C)<f(C′)。第十八頁(yè)，共三十九頁(yè)，編輯于2023年，星期二2．算法的偽代碼描述STRONGLY-CONNECTED-COMPONENTS(G)1for

u←1to

n2 do

order[u]←u3order←調(diào)用DFS-BY-ORDER(G,order)返回的top-logic數(shù)組4GT←TRANSPOSE-DIRECTED-GRAPH(G)5←調(diào)用DFS-BY-ORDER(GT,order)返回的數(shù)組TRANSPOSE-DIRECTED-GRAPH(G)1foreachuV

do2 AdjT[u]←NIL3foreachuV

do4 foreachv

Adj[u]do5 INSERT(AdjT[v],u)6return

GT第十九頁(yè)，共三十九頁(yè)，編輯于2023年，星期二DFS-BY-ORDER(G,order)1foreachvertexuV[G]2do

color[u]←WHITE3[u]←NIL4top-logic←S←5for

s←1ton6doif

color[order[s]]=WHITE7 then

color[order[s]]←GRAY8 PUSH(S,order[s])9 while

S≠

10 dou←TOP(S)11 ifvAdj[u]andcolor[v]=WHITE12 thencolor[v]←GRAY13 [v]←u14 PUSH(S,v)15 else

color[u]←BLACK16 PUSH(top-logic,u)17 POP(S)18 returnandtop-logic第二十頁(yè)，共三十九頁(yè)，編輯于2023年，星期二3．算法的運(yùn)行時(shí)間由于DFS-BY-ORDER的運(yùn)行時(shí)間與過(guò)程DFS的運(yùn)行時(shí)間相同都是Θ(V+E)，本章開(kāi)頭曾經(jīng)分析過(guò)計(jì)算GT的TRANSPOSE-DIRECTED-GRAPH的運(yùn)行時(shí)間也是Θ(V+E)。所以，過(guò)程STRONGLY-CONNECTED-COMPONENTS的運(yùn)行時(shí)間是Θ(V+E)。第二十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期二6.4無(wú)向圖的雙連通分支設(shè)G=(V,E)是一個(gè)連通無(wú)向圖。G的一個(gè)關(guān)節(jié)點(diǎn)是移除該點(diǎn)將導(dǎo)致該圖不連通的頂點(diǎn)。G的一座橋是G的一條邊，移除該邊將導(dǎo)致G不連通。G的一個(gè)雙連通分支是一個(gè)邊的最大集合，其中的任意兩條邊都同在一條簡(jiǎn)單環(huán)路上。第二十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期二1．問(wèn)題的理解與描述顯然，沒(méi)有關(guān)節(jié)點(diǎn)的圖G是雙連通圖。若兩個(gè)關(guān)節(jié)點(diǎn)u、v之間存在G的邊(u,v)，則(u,v)就是G的一座橋。刪除所有的橋，得到的G的子圖構(gòu)成G的雙連通分支。所以，計(jì)算圖的關(guān)節(jié)點(diǎn)是一個(gè)關(guān)鍵問(wèn)題，我們把它形式化為：輸入：無(wú)向連通圖G，G中一個(gè)頂點(diǎn)s作為源頂點(diǎn)。輸出：若G有關(guān)節(jié)點(diǎn)，返回G的關(guān)節(jié)點(diǎn)構(gòu)成的集合A，否則返回空集。第二十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期二2．關(guān)節(jié)點(diǎn)在DFS過(guò)程中的性質(zhì)(a)一個(gè)無(wú)向連通圖，其中頂點(diǎn)c、b、g和h是關(guān)節(jié)點(diǎn)（灰色頂點(diǎn)）。(b)以頂點(diǎn)b為源頂點(diǎn)進(jìn)行DFS得到的深度優(yōu)先樹(shù)（虛線邊為回邊），關(guān)節(jié)點(diǎn)之一的b成為樹(shù)根并有兩個(gè)孩子。(c)以頂點(diǎn)a為源頂點(diǎn)進(jìn)行DFS得到的深度優(yōu)先樹(shù)。作為關(guān)節(jié)點(diǎn)，無(wú)論在(b)或(c)中，只要不是樹(shù)根，都不會(huì)存在從孩子節(jié)點(diǎn)指向父親節(jié)點(diǎn)的回邊。第二十四頁(yè)，共三十九頁(yè)，編輯于2023年，星期二為了使DFS過(guò)程能跟蹤頂點(diǎn)是否具有關(guān)節(jié)點(diǎn)的性質(zhì)，我們定義深度優(yōu)先樹(shù)中節(jié)點(diǎn)v的屬性：對(duì)一個(gè)非根節(jié)點(diǎn)v而言，如果有它的孩子w的屬性low[w]不小于它的發(fā)現(xiàn)時(shí)間d[v]，則意味著v不存在后代有指向v的前輩的回邊。這樣，我們就可判斷v就是圖中的一個(gè)關(guān)節(jié)點(diǎn)。第二十五頁(yè)，共三十九頁(yè)，編輯于2023年，星期二3．算法的偽代碼描述ARTICULATION(G,s)1foreachvertexuV[G]2do

color[u]←WHITE3[u]←NIL4time←rootdegree←05A←S←6color[s]←GRAY7low[s]←d[s]←time←time+18PUSH(S,s)9while

S≠

10dou←TOP(S)11foreachvAdj[u]andcolor[v]=GRAY12do

low[u]=min{low[u],d[v]}13ifvAdj[u]andcolor[v]=WHITE14 thencolor[v]←GRAY15 [v]←u16 low[v]←d[v]←time←time+117 if

u=s18 then

rootdegree←rootdegree+119 PUSH(S,v)20 elsecolor[u]←BLACK21 POP(S)22for

v←1to

n23do

if

[v]NIL非根節(jié)點(diǎn)24then

if

low[π[v]]>low[v]25thenlow[π[v]]←low[v]26if

rootdegree>127then將s插入A根節(jié)點(diǎn)是關(guān)節(jié)點(diǎn)28foru←1to

n29doif

[u]s30thenif

low[u]

d[[u]]31then

將[u]插入A非根節(jié)點(diǎn)[u]是關(guān)節(jié)點(diǎn)32return

A由于過(guò)程ARTICULATION是基于DFS的計(jì)算無(wú)向連通圖的關(guān)節(jié)點(diǎn)，所以其時(shí)間復(fù)雜度和DFS的一樣，為Θ(V+E)。第二十六頁(yè)，共三十九頁(yè)，編輯于2023年，星期二6.5流網(wǎng)絡(luò)與最大流問(wèn)題我們可以把一個(gè)有向圖解釋為一個(gè)“流網(wǎng)絡(luò)”并利用它來(lái)回答關(guān)于物流的問(wèn)題。想象一個(gè)流動(dòng)于某系統(tǒng)的物流從生產(chǎn)出該物品的某源點(diǎn)出發(fā)，匯集于某消費(fèi)該物品的接收地。源點(diǎn)以不變的速率生產(chǎn)物品，匯點(diǎn)以相同的速率消費(fèi)該物品。系統(tǒng)中任一點(diǎn)的物“流”直觀地看就是在該點(diǎn)物品的移動(dòng)速率。流網(wǎng)絡(luò)可以用來(lái)模型化流過(guò)管道的流體，通過(guò)流水線的零部件，通過(guò)電網(wǎng)的電流，通過(guò)通信網(wǎng)絡(luò)的信息，等等。第二十七頁(yè)，共三十九頁(yè)，編輯于2023年，星期二1．問(wèn)題的理解與描述（1）流網(wǎng)絡(luò)。一個(gè)流網(wǎng)絡(luò)G=<V,E>是一個(gè)有向圖，其中的每一條邊(u,v)

E有一個(gè)非負(fù)的容量c(u,v)0。若(u,v)?E我們假定c(u,v)=0。即我們?cè)诰W(wǎng)絡(luò)中標(biāo)識(shí)兩個(gè)頂點(diǎn)：一個(gè)稱(chēng)為源點(diǎn)，記為s；一個(gè)稱(chēng)為匯點(diǎn)，記為t。假定每一個(gè)頂點(diǎn)都位于從源點(diǎn)到匯點(diǎn)之間的某條路徑上。即，對(duì)每一個(gè)頂點(diǎn)v

V，有一條路徑svt

。所以，該圖是連通的，且|E||V|-1。第二十八頁(yè)，共三十九頁(yè)，編輯于2023年，星期二（2）流設(shè)G=<V,E>是一個(gè)網(wǎng)絡(luò)，其容量函數(shù)為c。設(shè)s為該網(wǎng)絡(luò)的源點(diǎn)，t

是匯點(diǎn)。G中的一個(gè)流是一個(gè)實(shí)數(shù)值函數(shù)f：V×V→R它滿足如下3條性質(zhì)：容量約束：對(duì)所有的u,v

V,要求f(u,v)

c(u,v)。斜對(duì)稱(chēng)性：對(duì)所有的u,v

V,要求f(u,v)=-f(v,u)。流守恒性：對(duì)所有的u

V-{s,t},要求

。量f(u,v)，可以是正的、零或負(fù)的，稱(chēng)為是從頂點(diǎn)u到頂點(diǎn)v的流。一個(gè)流f的值定義為：第二十九頁(yè)，共三十九頁(yè)，編輯于2023年，星期二（3）最大流問(wèn)題在最大流問(wèn)題中，已知一個(gè)網(wǎng)絡(luò)G及其源點(diǎn)s和匯點(diǎn)t，希望找到具有最大值的流。形式化為：輸入：網(wǎng)絡(luò)G=<V,E>，其中源點(diǎn)為s，匯點(diǎn)為t，定義在VV上的容量c。輸出：定義在VV上的流f：VVR，使得

最大。第三十頁(yè)，共三十九頁(yè)，編輯于2023年，星期二（4）剩余網(wǎng)絡(luò)直觀地看，對(duì)給定的網(wǎng)絡(luò)及一個(gè)流，其剩余網(wǎng)絡(luò)由可以接受更多流的邊組成。更形式化地說(shuō)，假定有一個(gè)網(wǎng)絡(luò)G=<V,E>，其源點(diǎn)為s，匯點(diǎn)為t。設(shè)f為G中的一個(gè)流，考慮一對(duì)頂點(diǎn)u,v

V。不超過(guò)容量c(u,v)，從u到v可以添加的流量是(u,v)的剩余容量，定義如下：cf(u,v)=c(u,v)-f(u,v)給定一個(gè)流網(wǎng)絡(luò)G=<V,E>和一個(gè)流f，G的根據(jù)f的剩余網(wǎng)絡(luò)記為Gf

=<V,Ef>，其中Ef

={(u,v)

V×V:cf(u,v)>0}第三十一頁(yè)，共三十九頁(yè)，編輯于2023年，星期二（5）增廣路徑給定網(wǎng)絡(luò)G=(V,E)及一個(gè)流f，一條增廣路徑p是剩余網(wǎng)絡(luò)Gf中的一條從s到t的簡(jiǎn)單路徑。根據(jù)剩余網(wǎng)絡(luò)的定義，增廣路徑上的每一條邊(u,v)將接納一些從u到v的附加正流而不會(huì)違背該邊上的容量限制。定理6-6若f是G的一個(gè)最大流，則G關(guān)于f的剩余網(wǎng)絡(luò)Gf中不存在增廣路徑。第三十二頁(yè)，共三十九頁(yè)，編輯于2023年，星期二（6）流網(wǎng)絡(luò)的割流網(wǎng)絡(luò)G=(V,E)的一個(gè)割(S,T)是V的一個(gè)分為S和T=V–S，且s

S及t

T的一個(gè)劃分。若f是一個(gè)流，則跨越割(S,T)的凈流定義為

。割(S,T)的容量為

。一個(gè)網(wǎng)絡(luò)的最小割是該網(wǎng)絡(luò)的容量最小的割。引理6-7流網(wǎng)絡(luò)G中的任一個(gè)流f，以G的任一割的容量為上界。第三十三頁(yè)，共三十九頁(yè)，編輯于2023年，星期二2．算法的偽代碼描述定理6-7設(shè)流網(wǎng)絡(luò)G關(guān)于流f不存在增廣路徑，則f是G的一個(gè)最大流。EDMONDS-KARP(G,s,t,c)1f←f02cf←c3Gf←G4(,d)←BFS(Gf,s)5whiled[t]6 dop←由決定的從s到t的路徑7 cp←min{cf(u,v):(u,v)在p中}8 forp中的每條(u,v)9 dof[u,v]←f[u,v]+cp10 f[v,u]←-f[u,v]11 cf[u,v]←cf[u,v]-cp12 cf[v,u]←cf[v,u]+cp13