算法設(shè)計(jì)與分析第8-10章課件

1、第8章 分枝一限界法本章的內(nèi)容是回溯法討論的問題的繼續(xù)和擴(kuò)展。使用限界函數(shù)的深度優(yōu)先生成結(jié)點(diǎn)方法是回溯法，E結(jié)點(diǎn)一直保持到死為止的狀態(tài)生成方法叫分枝限界法。在這一章里，首先介紹狀態(tài)空間樹上的三種檢索方式：FIFO，LIFO，LC檢索，再重點(diǎn)介紹用LC-分枝限界法解最優(yōu)化問題的一般實(shí)現(xiàn)，最后得出一個(gè)實(shí)例0/1背包的解法以及用C語言實(shí)現(xiàn)的程序。8.1 狀態(tài)空間樹上的檢索FIFO，LIFO，LC檢索8.1.1 FIFO(first in first out)，LIFO(last in first out)檢索圖8.1 由FIFO分枝限界法生成的一部分4-后狀態(tài)空間樹8.1.2 LC-檢索在生成一個(gè)答

2、案結(jié)點(diǎn)之前，子樹X需要生成的結(jié)點(diǎn)數(shù)。在子樹X中，X到最近一個(gè)答案結(jié)點(diǎn)的路徑長。例8.1 15謎問題(15-puzzle)。在44的方格棋盤上,將數(shù)字1,2,3,15以任意順序放置在棋盤的各個(gè)方格中，空出一格,如圖8.2(a)為15謎問題的一種初始棋盤格局。定理8.1 對于一個(gè)給定的狀態(tài)圖8.2 15謎問題的一個(gè)實(shí)例如果這個(gè)和數(shù)是偶數(shù),則這個(gè)狀態(tài)可達(dá)目標(biāo)狀態(tài),否則,其他任何初態(tài)都不可達(dá)目標(biāo)狀態(tài)。圖8.3 15-謎問題的一部分狀態(tài)空間樹設(shè)想1：g(X)是結(jié)點(diǎn)X表示的狀態(tài)中沒有到達(dá)目標(biāo)位置的非空白牌的數(shù)目。顯然，狀態(tài)X到達(dá)目標(biāo)狀態(tài)所需要的移動(dòng)空白牌的次數(shù)大于g(X)。比如狀態(tài)X設(shè)想2： f (x)同

3、設(shè)想1， 這里j表示空格的位置。它也是一個(gè)可行的方法,似乎不及設(shè)想1中的g (X)好，因?yàn)閷D 8.3給定的初態(tài)，它需要產(chǎn)生更多的結(jié)點(diǎn)，但是如果檢索如8.1.3 LC-檢索的抽象化描述算法8.1的狀態(tài)空間樹，按設(shè)想1,g(1)=1,按設(shè)想2, g (1) = 14。這里f ( X ) +14=14顯然更接近C(X),C(X)是初態(tài)到目標(biāo)狀態(tài)的路徑長度,即需要移動(dòng)空白牌的次數(shù)。procedure LC(T，C)；begin ET；置活結(jié)點(diǎn)表為空；loop if E是答案結(jié)點(diǎn) then begin 輸出從E到T的路徑； return； end； for E的每個(gè)兒子結(jié)點(diǎn)X do begin cal

4、l add(x)； parent(x)E； end；if 不再有活結(jié)點(diǎn) then begin print(No answer node)； stop； end； call least(E)； repeat；endp；8.2 分枝限界法解最優(yōu)化問題例8.2 帶限期的作業(yè)排序問題。假定有n個(gè)作業(yè)Wi，i=1，n和一臺(tái)處理機(jī)，每個(gè)作業(yè)Wi與一個(gè)三元組(pi，di，ti)對應(yīng)，其中ti是完成作業(yè)Wi需要的時(shí)間，di是完成作業(yè)Wi需要的期限，如果不在這個(gè)期限di之內(nèi)完成Wi則將受到pi的罰款。問題的目標(biāo)是從n個(gè)作業(yè)中選取一個(gè)子集J，要求J中的作業(yè)都能在相應(yīng)的限期內(nèi)完成，且使不在J中的作業(yè)受到的罰款總額最

5、小,這樣的J就是最優(yōu)解。圖8.4 大小可變的元組表示對應(yīng)的狀態(tài)空間樹X中最小成本答案結(jié)點(diǎn)的上界函數(shù)u(X)定義為：圖8.5 大小固定的元組表示對應(yīng)的狀態(tài)空間樹以圖8.4元組大小不固定的狀態(tài)空間樹為例說明作業(yè)排序的LC-分枝限界算法。開始時(shí)置最小成本答案結(jié)點(diǎn)的成本上界U=,或由于圖8.4中每個(gè)圓形結(jié)點(diǎn)都是答案結(jié)點(diǎn)，按U的定義：算法8.2procedure LCBB(T，c，u，cost)/為了找出最小成本結(jié)點(diǎn),檢索狀態(tài)空間樹T,假定T至少包含一個(gè)解結(jié)點(diǎn),且C(X)C(X) u(X)/begin ET；parent(E)0； if T是解結(jié)點(diǎn) then begin Umin(cost(T)，u(T

6、)+)； ansT； endelse begin Uu(T)+； ans0； end；將活結(jié)點(diǎn)表初始化為空；loop for E的每個(gè)兒子 do if C(X)U then begin call ADD(X)； parent(X) E； case X是解結(jié)點(diǎn)and cost(X)U： begin Umin(cost(X)，u(X)+)； ansX； end； u(X)+UUu(X)+： endcase； end；if 不再有活結(jié)點(diǎn) or 下一個(gè)E-結(jié)點(diǎn)有CU then begin print(least cost=，U)； while ans0 do begin print(ans)； ans

7、parent(ans)； end； return； end； call least(E)； repeat；endp；對算法LCBB還需強(qiáng)調(diào)以下幾點(diǎn)：當(dāng)下一個(gè)E-結(jié)點(diǎn)使CU時(shí)，算法終止；子算法ADD是加入一個(gè)結(jié)點(diǎn)到活結(jié)點(diǎn)表中，LEAST是從一個(gè)活結(jié)點(diǎn)表中刪去一個(gè)結(jié)點(diǎn)，活結(jié)點(diǎn)表作成一個(gè)min堆；如果U是已找到的一個(gè)解X的成本值，U=c(X)u(X)，對于X的兒子Y，不僅c(Y)U，而且c(Y)=U的結(jié)點(diǎn)Y都要被殺死；如果U是一個(gè)單純的上界，它是由一可行結(jié)點(diǎn)X的u值修改而得，U=u(X)+。對于X的兒子只殺死c(Y)U的Y，c(Y)=U的Y不被殺死，Y入堆；雖然找到了一個(gè)答案結(jié)點(diǎn)X,但它的成本值大于

8、它的上界值u(X),這說明,這個(gè)答案結(jié)點(diǎn)的子孫中還有成本更小的答案結(jié)點(diǎn),U取u(X)+,對于X的兒子結(jié)點(diǎn)Y,只殺死c(Y)U的Y，c(Y)=U的Y不被殺死,Y入堆。8.3 0/1背包問題的LC-分枝限界求解的 實(shí)現(xiàn)例8.3 0/1背包問題。問題可描述如下：極小化：規(guī)范函數(shù) xi=0 或 xi=1, 1in成本函數(shù) 為了使最小成本答案結(jié)點(diǎn)與最優(yōu)解對應(yīng)，成本函數(shù)定義如下：如果X是答案結(jié)點(diǎn)，如果X是不可行的葉子結(jié)點(diǎn)，C(X)=；如果X是非葉子結(jié)點(diǎn),C(X)= minC(LCHI LD(X),C(RCHILD(X)。算法8.3procedure UBOUND(P，W，k，M)；/P：當(dāng)前效益總量;W:

9、當(dāng)前背包質(zhì)量;k:上次處理的物品的下標(biāo)號(hào);M:背包容量;W(i)：第i種物品的質(zhì)量;P(i):第i種物品的效益值,并且P(i)/W(i)P(i+1)/W(i+1),1in/begin bP；cW； for ik+1 to n do if c+ W(i)M then begin cc+W(i)； bb-P(i)； end； return(b)；endp；算法8.4算法中涉及的說明同算法8.3.procedure BOUND(P，W，k，M)；begin bP；cW； for ik+1 to n do begin cc+W(i)； if cM then bb-P(i) else return(b-

10、(1-(c-M)/W(i)*P(i)； end； return(b)；endp；圖8.6 0/1背包問題的一個(gè)實(shí)例的分枝限界檢索解決以下問題：被檢查的狀態(tài)空間樹中結(jié)點(diǎn)的結(jié)構(gòu)；如何生成一個(gè)兒子結(jié)點(diǎn)；如何識(shí)別答案結(jié)點(diǎn)；活結(jié)點(diǎn)表的表示以及其上的操作。算法8.51)計(jì)算上、下界Procedure LUBOUND(P,W,rw,cp,N,k,LBB,UBB),/rw：背包的剩余容量,cp：已獲得的效益,還有k，N個(gè)物品作選擇,LBB=-u(X),UBB=-C(X)/begin LBBcp；crw； for ik to N do begin if cW(i) then begin UBBLBB+c*P(i

11、)/W(i)； for ji+1 to N do if cW(j) then begin cc-W(j)； LBBLBB+P(j)； end； return； end； cc-W(i)； LBBLBB+P(i)； end； UBBLBB；endp；2)生成一個(gè)新結(jié)點(diǎn)Procedure NEWNODE(par，lev，t，cap，prof，ub)/生成一個(gè)新結(jié)點(diǎn)i，將它加入活結(jié)點(diǎn)表中/begin call GETNODE(i)； ARENT(i)par;LEVEL(i)lev;TAG(i)=t； CU(i)cap；PE(i)prof；UB(i)ub； call ADD(i)；endp；3)輸出解

12、procedure FINISH(L，ANS，N)begin for jN to 1 step-1 do begin if TAG(ANS)=1 then printf(j)； ANSPARENT(ANS)； end；endp；算法8.6procedure LCKNAP(P，W，M，N，)1 begin2 call INIT ；/初始可用結(jié)點(diǎn)表以及活結(jié)點(diǎn)表/3 call GETNODE(E)；/生成根結(jié)點(diǎn)/4 PARENT(E)0;LEVEL(E)1;CU(E)M；PE(E)0；5 call LUBOUND(P， W， M， N，0，1， LBB， UBB)；6 LLBB-；UB(E)UBB；

13、7 repeat8 iLEVEL(E)；capCU(E)；prof PE(E)；9 case10 i=N+1/解結(jié)點(diǎn)/11 if profL then12 begin13 Lprof；14 ANSE；15 end；16 iN+1/E有的兩個(gè)兒子/17 begin18 if capW(i) then /生成左兒子/19 ca ll NEWNODE(E，i+1，1，cap-W(i)，prof+p(i)，UB(E)； /看右兒子是否會(huì)成為活結(jié)點(diǎn)/20 call LUBOUND(P，W，cap，prof，N，i+1，LBB，UBB)；21 if UBBL then /右兒子會(huì)活/22 begin23

14、call NEWNODE(E，i+1，0，cap，prof，UBB)；24 Lmax(L，LBB-)；25 end；26 endcase；27 if 不再有活結(jié)點(diǎn) then exit；28 call LARGEST(E)；29 until UB(E)L；30 call FINISH(L，ANS，N)；31 endp；下面是該算法用C語言實(shí)現(xiàn)的程序清單。/* this is the fixed number */#define n 8#define lit 0.000 1#define m 110.0#define nn 20#define len sizeof(struct point)/*

15、this is the data structure */struct point int parent； int level； int tag； float cu； float pe； float ub；struct list struct point *dot； struct list bagnn； struct point *e； float apn，awn； float l，lbb，ubb； int pc，lpc，ans； int llnn；/* the more number*/float max(a，b)float a，b； float more； if (ab) more=a；

16、else more=b； return(more)；main( ) float cap，prof，x，y； Int i，j，k，la，jobok； void lubound( )； void newnode( )； void add()； void finish()； int largest()； printf(* this is a programme about 0/1 bag problem * n)； printf(input p and w !n)； for (i=0；i=n-1；i+) scanf(%f，&x)； scanf(%f，&y)； j=0； while (j=i-1) &

17、 (x/y)(apj/ awj) j=j+1； for (k=i；k=j+1；k-) apk=apk-1 ； awk=apk-1 ； apj=x；awj=y； jobok=0； pc=0； lpc=0； e=(struct point *) malloc(len)； e-parent=-1；e-level=1;e-cu=m； e-pe=0.0；e-tag=-1； la=0； lubound(m，0.0，0)； l=lbb-lit； e-ub=ubb； bagpc.dot=e； ans=0； do i=e-level;cap=e-cu；prof=e-pe； if (i=n+1) printf(*

18、 the best result is： * *n)； if (profl) l=prof；ans=la； else if (cap=awi-1) newnode(la，i+1，1，cap-awi-1， rof+api-1，e-ub)； lubound(cap，prof，i)； if (ubbl) newnode(la,i+1,0,cap,prof,ubb)； l=max(l，lbb-lit)； if (lpc= =0) printf(the num of livelist is %dn，lpc)；jobok=1；break； if (!jobok) la=largest()； e=bagla

19、.dot； while(e-ub)l) ； finish(ans，l)； printf( * my programme have finished *n)；/* the bound of the point */void lubound(rw，cp，k)float rw，cp；Int k； int i，j； float c； lbb=cp；c=rw； for (i=k；i=n-1；i+) if (cawi) ubb=lbb+c*api/awi； for (j=i+1；j=n-1；j+) if (c=awj) c=c-awj； lbb=lbb+apj； goto exit； c=c-awi；lb

20、b=lbb+api； ubb=lbb；exit ； /* add to livelist */void add(y)Int y； int j，addok； lpc=lpc+1； addok=0； j=lpc； while (! addok) & (j1) if (bagy.dot-ub)=(bagll j/2. dot-ub) llj=llj/2； j=j/2； else addok=1； llj=y； /* delete the largest number from the livelist and form the max-stock again */int largest() int

21、lar，i，j，t，delok； lar=ll1； ll1=lllpc； lpc=lpc-1； i=1； j=2*i； t=ll1； delok=0； while (j=lpc) & (!delok) if (jlpc) & (bagllj.dot-ub)(bagllj+1.dot-ub) j=j+1; if(bagt.dot-ub)=(bagllj. dot-ub) delok=1； else lli=llj； i=j； j=2*i； lli=t； return(lar)；/* NEWNODE form a new point */void newnode(par，lev，t，cap，pro

22、f，vub)int par，lev，t；float cap，prof，vub； pc=pc+1； e =(struct point *) malloc(len)； e-parent=par； e-level=lev； e-tag=t； e-cu=cap； e-pe=prof； e-ub=vub; bagpc.dot=e； add(pc)； /* print the result */void finish(ans，l)Int ans；float l； printf(VALUE OF OPTIMAL FILLING IS ：%fn, l)； printf(OBJECTS IN KNAPSACK

23、ARE:)； while (ans0) if (bagans.dot-tag= =1) rintf(% d-，bagans.dot-level-1)； ans=bagans.dot-parent； printf(endn)；第9章 內(nèi)存分類法分類也叫排序。根據(jù)待分類的記錄的數(shù)量的多少，可將分類分為兩類：一類是內(nèi)存分類，這種分類是指待分類的記錄的關(guān)鍵字的數(shù)量不是很多，可一次調(diào)入計(jì)算機(jī)的內(nèi)存進(jìn)行分類；另一類是外存分類，這種分類指的是待分類的數(shù)據(jù)的數(shù)量很大，內(nèi)存一次不能容納全部數(shù)據(jù)，在分類過程中，需要進(jìn)行內(nèi)外存的交換進(jìn)行分類的過程。本章介紹的是第一種,但只介紹內(nèi)存分類法中兩個(gè)問題:求第K個(gè)元素(也叫

24、順序統(tǒng)計(jì));另一個(gè)是堆排序。9.1 求第K個(gè)元素圖9.1 錦標(biāo)賽過程示意圖算法9.1 找出序列S=x1，x2，xn的第K小元素。輸入：有n個(gè)元素的序列S以及整數(shù)K，1 Kn；輸出： S的第K小元素。pocedure Kthmin(S，K)；begin if S64 then begin sort S; /任一種分類法,對S直接分類/ return S的第K小元素； endelse begin 將S分成 個(gè)子序列，每個(gè)子序列有15個(gè)元素。如果有剩余元素放入子序列L，對它們分別進(jìn)行分類；設(shè)C是15個(gè)元素子序列的中值組成的序列； mKthmin(C， c/2 )； /求m的序數(shù)/ if m的序數(shù) =

25、K then return m else if m的序數(shù)K then Kthmin(S-A，k1=K-A) else Kthmin(S-B，k)； end；endp；對算法9.1的了解可參考圖9.2，不妨設(shè)n剛好是15的倍數(shù)。設(shè)T(n)是從S(S=n)中選出第K小元素所需時(shí)間，則圖9.2 算法9.1的示意圖解這個(gè)遞歸式 T(n)=O(n)。算法9.2 尋找序列S的第K小元素。Procedure quickmin(S，K)；begin if S=1 then return S中的單個(gè)元素 else else begin 從S中隨機(jī)地選出一個(gè)元素a； 用快速分類法求出S1，S2，S3； /S1：小

26、于a的元素序列；S2：等于a的元素序列；S3：大于a的元素序列；/ if S1K then return quickmin(S1，K) else if S1+S2K then return a else return quickmin(S3,K-S1-S2);end；endp；假設(shè)T(n)是對長度為n的序列S求第K小元的平均時(shí)間耗費(fèi)。S中的n個(gè)元素xi是互不相同的。在利用快速分類時(shí)，作為“樞軸”的元素a是S的第i個(gè)最小元，其中i=1，2，n是等概率的。如果iK，則在S1上調(diào)用quickmin的時(shí)間耗費(fèi)為：O(n)+T(i-1)；如果iK，則在S3上調(diào)用quickmin的時(shí)間耗費(fèi)為：O(n)+T

27、(n-i)；如果i=K，時(shí)間耗費(fèi)為：O(n).當(dāng)i遍取1，2，n時(shí)，可選T(1)c，用歸納法證明：對于所有n2，有T(n)4cn。對于n=2，有 T(1)=3c4c2；假定有T(n)4cn，對所有的n，2nm成立；對于n=m由于T(n)是n的非降函數(shù),因此當(dāng) 時(shí), 取極大值，所以所以T(n)4cn成立，即T(n)=O(n)。9.2 堆 分 類在數(shù)據(jù)結(jié)構(gòu)中已作介紹,當(dāng)待分類的元素沒有明顯的結(jié)構(gòu)特征時(shí),只能施行“比較”操作,以此確定兩個(gè)元素的順序。這種“比較”分類,理論上已證明至少需要作log2n!次比較,而log2n!nlog2n-1.44n+log2 +1.325，此作為比較分類的時(shí)間復(fù)雜性的

28、理論下界。設(shè)A=a1，a2，an是待分類的序列，T是一棵二叉樹，T中每個(gè)結(jié)點(diǎn)都對應(yīng)著A中的一個(gè)元素。T是一個(gè)極大/極小堆，當(dāng)且僅當(dāng)滿足以下條件：T是一棵完全二叉樹；aia2i且aia2i+1 或 aia2i且aia2i+1 (i=1，2，n/2).利用堆可以將待分類的序列A分類，其基本步驟是：將A建成堆；A1An；置nn-1，即在T中把極大結(jié)點(diǎn)輸出，得到一棵非堆的二叉樹；恢復(fù)堆。在當(dāng)前T中，將根結(jié)點(diǎn)(或子樹的根結(jié)點(diǎn))與它的兩個(gè)兒子結(jié)點(diǎn)中較大的結(jié)點(diǎn)交換,直到每個(gè)結(jié)點(diǎn)都大于它的子孫為止；重復(fù)、，直到n=1，將輸出分類后的結(jié)果。這種分類方法叫堆分類。1)建立初始堆算法9.3procedure HEA

29、PFIFY(i，j)；/將數(shù)組元素AiAj建成堆/begin while (2i+1j)(AiA2i )(AiA2i+1) do /i不是一片葉子且若i的兒子含有比i大的元素/ begin if(A2iA2i+1)then begin Ai A2i； HEAPFIFY(2i，j)； end else begin AiA2i+1； HEAPFIFY(2i+1，j)； end； if(2i=j)(AiA2i) then Ai A2i； end； endp；算法9.4Procedure BUILDHEAP；begin for i n/2step-1 until 1 do call HEAPFIFY(

30、i，n)；endp；2)分類算法9.5 Heapsort：輸入：待分類的數(shù)組Ai，1in；輸出：已分類的數(shù)組A。procedure Heapsort；begin call BUILDHEAP； mn； while m1 do begin AiAm；mm-1；call HEAPFIFY(1，m)； end；endp；對于深度為K的堆,HEAPFIFY進(jìn)行關(guān)鍵字比較的次數(shù)至多為2(k-1)次,則在建含有n個(gè)元素，深度為h的堆時(shí),由于第i層上的結(jié)點(diǎn)數(shù)至多為2i-1,以它為根的完全二叉樹的深度為h-i+1。則調(diào)用n/2次HEAPFIFY總共進(jìn)行的關(guān)鍵字比較次數(shù)不超過下式之值：對于堆分類,每次調(diào)用HEA

31、PFIFY算法的比較次數(shù)最多是深度的2倍,即2 log2m,2 mn-1，所以總的比較次數(shù)是：圖9.3 初始堆示例算法9.6procedure UPANDUP(i，j)；begin if i不是葉子 then begin 令k是i的帶有較大元素的兒子； AiAk； call UPDANDUP(k，j)； endelse begin Ai Aj+1； /將最后一片葉子放在完全二叉樹中當(dāng)前所缺的葉子結(jié)點(diǎn)上。如果所缺的葉子剛好是完全二叉樹上的最后一片葉子，則將最后一片葉子自己賦給自己/ while AiA i/2 do begin Ai A i/2； i i/2； end； end；endp；算法9

32、.7procedure Heapsort1；begin call BUILDHEAP； for jn step-1 until 2 do begin BA1；call UPANDUP(1，j-1)；AjB； end；endp；下面對Heapsort1進(jìn)行時(shí)間復(fù)雜性分析：初始堆之后，為了輸出分類序列，用了15次比較圖9.4 Heapsort的實(shí)現(xiàn)過程初始堆之后，為了輸出分類序列，用了9次比較圖9.5 Heapsort1的實(shí)現(xiàn)過程算法9.8procedure UPORDOWN(i，j)；begin if id then begin 令k是i的較大兒子； AiAk； call UPORDOWN(k，

33、j)； end else begin AiAj+1； if AiA i/2 then call HEAPFIFY(i，j) else while AiA i/2 do begin AiA i/2； i i/2； end； end；endp；算法9.9procedure Heapsort2；begin call BUILDHEAP； for jn step-1 until 2 do begin d2 ；BA1; UPOR DOWN(1，j-1)； AjB； end；endp；同上對Heapsort1的分析，算法9.9的時(shí)間耗費(fèi)包括兩部分：調(diào)用BUILDHEAP，初始化堆，其耗費(fèi)是O(n)。for

34、循環(huán)的耗費(fèi)。第10章 圖的算法圖是應(yīng)用極為廣泛的數(shù)學(xué)工具。許多工程和科學(xué)技術(shù)中的問題可以抽象為圖，將圖作為其數(shù)學(xué)模型。圖的研究分為兩類：一是圖論，研究圖的一些代數(shù)性質(zhì)；二是圖的應(yīng)用，主要研究圖的最優(yōu)化問題。本章介紹這兩方面的一些基本算法。10.1 圖的兩種遍歷DFS，BFS圖本身是一種無序結(jié)構(gòu)。在解決圖的問題時(shí),幾乎所有算法都需要處理圖的頂點(diǎn)或邊, 為了盡可能少地對頂點(diǎn)和邊作重復(fù)檢查,需要人為地規(guī)定圖的檢索順序。在數(shù)據(jù)結(jié)構(gòu)中已介紹過圖的遍歷的兩種方式DFS（Depth First Search）遍歷和BFS（Breadth First Search)遍歷兩種方式,這兩種方式實(shí)際上都是對圖這種無

35、序結(jié)構(gòu)作線性化處理。算法10.1 dfs的遞歸算法。Procedure dfsrecursive（G，v）。begin 訪問v；標(biāo)記v； while有一個(gè)鄰接于v的未標(biāo)記的頂點(diǎn)w do dfsrecursive（G，w）；endp；算法10.2 dfs的非遞歸算法。Procedure dfs（G，v）；/S是一個(gè)棧，初始為空，在任何時(shí)候，棧頂元用top表示/begin 訪問v；標(biāo)記v；push（S，v）； while S非空 do begin while top有鄰接點(diǎn)w且w未標(biāo)記 do begin 訪問w；標(biāo)記w；push（S，w）; end； pop（S）； end；endp；算法10.3

36、Procedure bfs（G，v）；/Q是一個(gè)隊(duì)列，初始為空/begin 訪問v；標(biāo)記v；enqueque（Q，v）； while Q非空do begin xdelqueque（Q）； for 每個(gè)鄰接于x而未標(biāo)記的頂點(diǎn)w do begin 訪問w；標(biāo)記w； enqueque（Q，w）； end； end；endp；上述算法僅訪問了以v為始點(diǎn)，以及v的可達(dá)頂點(diǎn)，如果要訪問G中每個(gè)頂點(diǎn)，則算法10.4 圖的遍歷。Procedure travel（G）；begin for v1 to n do v標(biāo)記0； for v1 to n do if v未標(biāo)記 then dfs/bfs（G，v）；endp

37、；10.2 DFS 樹在一個(gè)圖（有向圖或無向圖）上作DFS時(shí)，引向未標(biāo)記頂點(diǎn)的邊構(gòu)成一棵有限樹稱為DFS樹，這種邊稱為樹邊。如果從始點(diǎn)出發(fā)，圖中所有頂點(diǎn)不是始點(diǎn)的可達(dá)頂點(diǎn)，則對圖的遍歷生成DFS森林。對于無向圖，這種搜索給圖的每條邊一個(gè)定向，按通過邊的方向?qū)叾ㄏ颉Ｈ绻怯邢驁D，則只能按預(yù)先給定邊的方向?qū)呥M(jìn)行訪問。算法10.5 求圖G的DFN數(shù)組Procedure dfsDFN（G，v）；/G的存儲(chǔ)用鄰接表l/var t：link；begin visit（v）；markv1；DFNvx; xx+1； t1v；（a）有向圖G （b）有向圖G的DFS森林圖10.1 while tnil do b

38、egin if markt，v=0 then dfs-DFN（G，t，v）； tt.next； end；endp；Procedure travel（G）；begin for v1 to n do markv0； x1； for v1 to n do if markv=0 then gfs2（v）；endp；頂點(diǎn)的深度優(yōu)先數(shù)與頂點(diǎn)的先輩后代關(guān)系的關(guān)系如下，以此去識(shí)別G的四種類型的邊：如果w是v的后代，則：DFN(v)DFN（y）；如果有向邊（x，y）是子孫邊，則：DFN（x）DFN（y）。如果x,y不滿足,則x,y是兄弟關(guān)系,或?qū)儆诓煌倪B通分支,所以和用來判定橫跨邊, 、則作為判定回邊與子孫邊

39、。10.3 無向圖的雙連通分支定義10.1 設(shè)G=(V，E)是一個(gè)連通的無向圖，頂點(diǎn)aV,如果存在頂點(diǎn)v,wV和a互不相同，并且v和w之間的每一條路徑都包含a, 則稱a是圖的一個(gè)關(guān)節(jié)點(diǎn),也叫圖的割點(diǎn)。定義10.3 E上的一個(gè)等價(jià)關(guān)系R定義為：e1Re2 e1=e2或者G中有一個(gè)回路既包含e1又包含e2。定義10.4 等價(jià)關(guān)系R將E分成等價(jià)類，E1，E2，Ek，使得兩條不同邊在同一個(gè)類當(dāng)且僅當(dāng)它們位于同一個(gè)回路上。設(shè)Vi是Ei中邊的關(guān)聯(lián)頂點(diǎn)集，每個(gè)圖Gi=（Vi，Ei）是G的一個(gè)雙連通分支。例10.1 圖10.2（a）是一無向圖。B，E，F(xiàn)是關(guān)節(jié)點(diǎn)，G有4個(gè)雙連通分支，位于公共回路的邊的等價(jià)類是

40、：（a）圖G （b）G的4個(gè)雙連通分支圖10.2E1=(G,B),(B，I),(I，G)E2=(B,E),(E，C),(C，B)E3=(E,F)E4=(H,E),(E,I),(H,A),(A，F(xiàn)),(F,D),(A,D),(I,D)有幾點(diǎn)注意：一條邊（例如E3）沒有回路，也產(chǎn)生一個(gè)雙連通分支。R是E上的等價(jià)關(guān)系,R對E產(chǎn)生一個(gè)分劃,并不對V產(chǎn)生分劃,因此一個(gè)頂點(diǎn)可能在幾個(gè)分支中,比如,B現(xiàn)在G1=（E1,V1）又出現(xiàn)在G2=（E2,V2）中。算法10.6 計(jì)算無向圖G計(jì)算low數(shù)組。Procedure dfs-low(G,k)；/假定G用鄰接表l存儲(chǔ),mark,low,DFN,father數(shù)組

41、分別是標(biāo)記數(shù)組,low數(shù)組和DFS數(shù)數(shù)組,以及頂點(diǎn)的父親。/圖10.3 DFS樹T中的一個(gè)關(guān)節(jié)點(diǎn)Vvar t：link；begin markk1；DFNkx；xx+1; lowkDFNk；t1k； while tnil do begin if markt.k=0 then begin fathert.kk； dfs-low（t.k）； lowkminlowk，lowt.k； /如果頂點(diǎn)k在dfs樹中有一個(gè)兒子w=t.k,且low（w） DFN（top） do begin tag（x）1；output x； pop（SC）； end； /輸出一個(gè)強(qiáng)連通分支/end else begin push

42、（SC，top）； ZS上的第二個(gè)頂點(diǎn)（從top起） low(Z)minlow(Z)，low(top) end； pop（S）； /從top返回到Z，即新的top/ if S不空 then goto forward； endp；10.5 流 的 算 法許多系統(tǒng)涉及流量問題，比如車輛運(yùn)行系統(tǒng)中的車流，控制系統(tǒng)的信息流，金融系統(tǒng)的金融流等，這些研究對象抽象為數(shù)學(xué)問題時(shí)，數(shù)學(xué)模型是網(wǎng)絡(luò)中的流。它本身屬于運(yùn)籌學(xué)和組合數(shù)學(xué)討論的內(nèi)容，本節(jié)內(nèi)容作為有向圖的應(yīng)用。10.5.1 基本概念（1）網(wǎng)絡(luò)與流定義10.5 G=(V,E)是一帶權(quán)的有向圖,在V中指定了一點(diǎn)稱為發(fā)點(diǎn)(source),vs以表示;指定 了另一點(diǎn)稱為收點(diǎn)(sink),以vt表示;其余的點(diǎn)叫中間點(diǎn)。G中邊上的權(quán)大于或等于0,稱為弧的容量,記為C(vi，vj),簡記為Cij。所謂網(wǎng)絡(luò)上的流,是指定義在E上的一個(gè)函數(shù)f=f(vi，vj),稱f (vi,vj)(簡記為fij)為弧(vi,vj)上的流量,f稱為網(wǎng)絡(luò)G上的一個(gè)流,如圖10.8。(a) 網(wǎng)絡(luò)G，邊上的數(shù)表弧的容量Cij(b) G上的一個(gè)流，邊上的數(shù)表弧的流量fij圖10.8 網(wǎng)絡(luò)上的流(2)可行流與最大流在網(wǎng)絡(luò)的實(shí)際問題中，對于流有兩個(gè)明顯的要求：一