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

算法導(dǎo)論復(fù)習(xí)筆記Chapter 22 基本圖算法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加入新圖，并將markv設(shè)置為true；否則就跳過。復(fù)雜度O(E)再次遍歷u的連邊，將markv初始化整體復(fù)雜度O(V+E)偽代碼:SOLVE(G,G)1 for each vetex uG2 for each v G.Adju3 if markv=false4 markv=true5 Addedge(G,u,v)6 for each vG.Adju7 markv=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)判斷是否存在一個(gè)數(shù)k，使得對(duì)所有的i有Aik=1,對(duì)所有的j有Akj=0,(ik,jk)令i和j初值為1，若Gij=0,說明i到j(luò)無邊，j不可能是通用匯點(diǎn)，令j=j+1;若Gij=1,說明i到j(luò)有邊，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)1 i=j=12 while iV and jV3 if Gij=14 i=i+15 else j=j+16 if iV7 return false8 else return CHECK(G,i)CHECK(G,u)1 for each vertex vG.V2 if Guv=13 return false4 for each vertex v G.V5 if Gvu=0& u!=v6 return 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)，都要遍歷所有的節(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之間的最短路徑就是直徑。時(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í)間，并給出每條邊的分類qrstuvwxyzdis/fin1/1617/202/78/1518/193/64/59/1213/1410/11qssvvwwsqwqttxxzzxtyyqryuyru樹邊樹邊樹邊后向邊前向邊樹邊樹邊樹邊后向邊樹邊后向邊橫向邊橫向邊樹邊22.3-7 用棧實(shí)現(xiàn)DFS，寫出偽代碼DFS-VISIT(G,u)1 STACK.PUSH(u)2 while(! STACK.empty)3 u=STACK.top4 if u.color=GRAY5 u.color=BLACK6 time=time+17 u.f=time8 STACK.POP9 continue10if u.color=WHITE11u.color=GRAY12time=time+113u.d=time14for each vG: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出，則最后回到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)繼續(xù)遍歷，會(huì)形成一個(gè)以s1為起始點(diǎn)（也是終止點(diǎn)）的子回路，這兩個(gè)回路沒有公共邊，而這兩個(gè)子回路明顯可以合并為一個(gè)回路，該回路為s-e-s1-f-s1-s, 這樣不斷擴(kuò)展就必然形成一個(gè)歐拉回路。b. 從任意點(diǎn)開始DFS并在DFS過程中保存回路上的邊。DFS的復(fù)雜度是O(E)的。23.1-5 設(shè)e為連通圖G的某條環(huán)路上權(quán)重最大的邊，證明：圖G=(V,E-e)中存在一棵最小生成樹，它也同時(shí)是G的最小生成樹。也就是說，G中存在一棵不包含邊e的最小生成樹。證明：反證。假設(shè)G中所有最小生成樹都包含e。任取一個(gè)這樣的最小生成樹T，在T上去掉e，將T分為兩棵子樹T1和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 第三種最小生成樹算法。c. MayBE-MST-C(G,w)1 T=空集2 for each edge e, taken in arbitrary order3 T=Te4 if T has a cycle c5 let e be maximum-weight edge on c6 T=T-e7 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的MST T同時(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é)