算法導(dǎo)論-復(fù)習(xí)筆記

1、算法導(dǎo)論復(fù)習(xí)筆記Chapter22基本圖算法22.1-1有向圖鄰接鏈表，計(jì)算節(jié)點(diǎn)出度和入度的時(shí)間復(fù)雜度？O(V+E)開一個(gè) degree數(shù)組，大小為結(jié)點(diǎn)個(gè)數(shù)，復(fù)雜度O(V);遍歷鄰接鏈表，經(jīng)過邊uv 時(shí)，計(jì)算出度degreeu+=1,計(jì)算入度 degreev+=1,復(fù)雜度 O(E)22.1-4將一個(gè)多圖變成等價(jià)無向圖，用鄰接鏈表表示，時(shí)間復(fù)雜度O(V+E)多圖是允許重復(fù)邊和自循環(huán)邊的圖。開一個(gè) bool 數(shù)組 mark, 大小為節(jié)點(diǎn)個(gè)數(shù)，初始化為 false 。復(fù)雜度 O(V) 。對(duì)每個(gè)頂點(diǎn) u 的鄰接鏈表，遍歷，令v 為 u 的邊所指向的頂點(diǎn)；如果 markv=false，將 uv加入新圖，

2、并將 markv 設(shè)置為 true ；否則就跳過。復(fù)雜度 O(E)再次遍歷 u 的連邊，將 markv 初始化整體復(fù)雜度 O(V+E)偽代碼 :SOLVE( G,G )1 for each vetex u G2for each v G.Adju3if markv=false4markv=true5Addedge(G ,u,v)6for each v G.Adju7markv=false22.1-6圖 G 的鄰接矩陣表示，給出一個(gè)O(V) 的算法來判斷有向圖G 中是否存在一個(gè)通用匯點(diǎn)。通用匯點(diǎn)指的是入度|V|-1 ，但出度為0。等價(jià)問題：給定有向圖G 的 VV 鄰接矩陣 G，在 O(V) 時(shí)間內(nèi)

3、判斷是否存在一個(gè)數(shù)k ，使得對(duì)所有的 i 有 Aik=1,對(duì)所有的 j 有 Akj=0,(ik,j k)令 i 和 j 初值為 1，若 Gij=0,說明 i 到 j 無邊， j 不可能是通用匯點(diǎn)，令j=j+1; 若 Gij=1,說明 i 到 j 有邊， i 不可能是通用匯點(diǎn)，令 i=i+1 ，循環(huán)直到 i|V| 或者 j|V|; 若 i|V| ，則不存在通用匯點(diǎn)，若 j|V| ，則檢查頂點(diǎn) i 是否滿足要求。偽代碼：判斷是否存在通用匯點(diǎn)O(V)HAS_UNIVERSL_SINK(G)i=j=1while i V and j Vif Gij=14i=i+1else j=j+1if iVretur

4、n falseelse return CHECK(G,i)CHECK(G,u)1 for each vertex v G.V2if Guv=13return false4 for each vertex v G.V5ifGvu=0& u!=v6return false7 return true檢查點(diǎn) u 是否是通用匯點(diǎn)【寬度優(yōu)先搜索】22.2-2計(jì)算無向圖BFS 后的 d 值和 值簡單，注意初始節(jié)點(diǎn)u 的值寫 NIL 或者寫 -1rstuvwxyD 值43105211值swuNILrtuu22.2-4輸入如果是鄰接矩陣表示的，BFS 的運(yùn)行時(shí)間？O(V2)對(duì)于隊(duì)列中的每一個(gè)節(jié)點(diǎn)，都要遍歷所有的

5、節(jié)點(diǎn)來判斷是否有邊。22.2-6 舉例說明一個(gè)有向圖 G 中可能存在這樣一個(gè)邊集 E： s 到 v 的唯一簡單路徑也是一條最短路徑，但是無論如何該邊集 E都不能通過在圖 G 上運(yùn)行 BFS 獲得。V=1,2,3,4,5,E=(1,2),(2,3),(1,4),(4,5),(2,5),(3,4), E=(1,2),(2,3),(1,4),(4,5), s=122.2-8求一棵樹 T=(V,E) 的直徑，并分析算法的運(yùn)行時(shí)間。直徑指的是樹中所有最短路徑的最大值。兩遍BFS 就能解決.設(shè) v 任意一點(diǎn)，BFS(v)，令u=v能到達(dá)的最遠(yuǎn)點(diǎn)。再BFS(u) ，取w 為u 能達(dá)到的最遠(yuǎn)點(diǎn)，則u 和w之間

6、的最短路徑就是直徑。時(shí)間復(fù)雜度是O(V+E)。注意本題的證明。反證法，設(shè)t1到t2是直徑，u是v 能達(dá)到的最遠(yuǎn)點(diǎn)，但是u 不是t1或者t2中的一個(gè)，產(chǎn)生矛盾的結(jié)論?！旧疃葍?yōu)先搜索】22.3-2給出 DFS 每個(gè)結(jié)點(diǎn)的發(fā)現(xiàn)時(shí)間和完成時(shí)間，并給出每條邊的分類dis/finq1/16r17/20s2/7t8/15u18/19v3/6w4/5x9/12y13/14z10/11qssvvwwsqwqttxxzzxtyyqryuyru樹邊樹邊樹邊后向前向樹邊樹邊樹邊后向樹邊后向橫橫樹邊邊邊邊向向邊邊邊22.3-7用棧實(shí)現(xiàn) DFS ，寫出偽代碼DFS-VISIT(G,u)STACK.PUSH(u)while

7、(! STACK.empty)u=STACK.topif u.color=GRAY5u.color=BLACK6time=time+17u.f=time8STACK.POP9continue10if u.color=WHITE11u.color=GRAY12time=time+113u.d=time14for each v G:Adju15if v.color=WHITE16v.=u17STACK.PUSH(v)22.3-8 舉出一個(gè)反例反駁：有向圖G 包含 u 到 v 的路徑，并且 DFS 時(shí) u.dw-v，且 du 若強(qiáng)連通有向圖G 有歐拉回路，則可知對(duì)于出發(fā)點(diǎn)s，假設(shè)有 x 次從 s 出

8、，則最后回到s必須恰好有x 次，因此對(duì)于s，出度和入度必然相等。假設(shè)對(duì)于某個(gè)非出發(fā)點(diǎn)v，出度與入度不相等；假設(shè)出度y 大于入度 x，則第 x 次從 v 離開后再也不能回到v，剩余的y-x 條邊不能被訪問到；假設(shè)出度y 小于入度 x，則第 y+1 次進(jìn)入v后無法出去。由此可知，對(duì)于非出發(fā)點(diǎn)v，入度與出度同樣相等。因此G 有Euler回路則入度等于出度成立。v1-v2- -vi 的路徑，其中vi 不等于 s，則遍歷過程中進(jìn)入vi 的次數(shù)比從vi 走出的次數(shù)多一次，這樣就肯定有一條從vi 出去的邊沒有被訪問到。所以不成立。這樣遍歷一次后會(huì)形成一個(gè)子回路，再在這個(gè)子回路上某個(gè)不同于s 點(diǎn)的 s1 點(diǎn)繼

9、續(xù)遍歷，會(huì)形成一個(gè)以s1 為起始點(diǎn)（也是終止點(diǎn)）的子回路，這兩個(gè)回路沒有公共邊，而這兩個(gè)子回路明顯可以合并為一個(gè)回路，該回路為s- -e-s1-f-s1- -s, 這樣不斷擴(kuò)展就必然形成一個(gè)歐拉回路。從任意點(diǎn)開始 DFS 并在 DFS 過程中保存回路上的邊。DFS 的復(fù)雜度是 O(E) 的。23.1-5設(shè) e 為連通圖小生成樹，它也同時(shí)是G 的某條環(huán)路上權(quán)重最大的邊，證明：圖G =(V,E-e) 中存在一棵最G 的最小生成樹。也就是說，G 中存在一棵不包含邊e 的最小生成樹。證明：反證。假設(shè)G 中所有最小生成樹都包含e 。任取一個(gè)這樣的最小生成樹T，在 T 上去掉 e ，將T 分為兩棵子樹T1

10、 和 T2， T1 上頂點(diǎn)集合為V1 ，T2 上頂點(diǎn)集合為V2 ，則 (V1,V2) 是一個(gè)割。e 所在的圈至少穿越割(V1,V2) 兩次， C 至少有 2 條邊在 (V1,V2) 中，其中一條邊是e。令 e為除了e 之外的另外一條邊，則w( e )w(e)。將 e 并到T1和T2上，將T1和T2連接成一棵新的生成樹T。由于T是在T 上去掉e、加入e后形成的，因此w( T)w(T) 。因此 ,T也是G 的一棵最小生成樹，且T中不包含e ，與假設(shè)矛盾。23-4 第三種最小生成樹算法。MayBE-MST-C(G,w) 1T= 空集2for each edge e,taken in arbitrar

11、y orderT=T eif T has a cycle c5let e be maximum-weight edge on c6T=T-e 7 return T證明：算法實(shí)際上是在圖G 中刪除一些圈上權(quán)值最重的邊，最后得到一棵MST 。設(shè)刪除的邊依次是e1,e2,em-n+1,剩余的圖一次是G0,G1,.,Gm-n+1，其中G=G0,Gm-n+1=T, m=|E|，n=|V|。證明 Gi+1 的 MST 同時(shí)也是 Gi 的 MST 即可。前面 23.1-5已經(jīng)證明存在Gi+1 的 MSTT 同時(shí)也是Gi 的 MST ，而 Gi+1 的所有 MST 的大小與T一樣，所以它們都與Gi的MST大小一樣，所以它們都是Gi的MST。從而Gm-n+1必然是Gm- n, ,G0的MST 。23-1 次優(yōu)最小生成樹每次從最小生成樹里換掉一條邊，用不在最小生成樹中的一邊代替。23-3 瓶頸生成樹最小生成樹是瓶頸生成樹。24.1-6 假定 G 為一個(gè)帶權(quán)重的有向圖，并且圖中存在一個(gè)權(quán)重為負(fù)值的環(huán)路。給出一個(gè)有效算法列出所有屬于該環(huán)路上的結(jié)點(diǎn)。證明正確