數(shù)據(jù)結(jié)構(gòu)課件：16 【習(xí)題課】第5章

1、第五章習(xí)題15-1 給出有向圖的鄰接矩陣和鄰接表0 0 1 1 00 0 1 1 00 0 0 0 10 0 0 0 01 0 0 1 0ABCDCDADCDEE2權(quán)圖： 對(duì)應(yīng)邊的權(quán)值，若無(wú)邊，則為無(wú)窮非權(quán)圖： 0或1習(xí)題5-7用鄰接矩陣存儲(chǔ)一個(gè)包含1000個(gè)頂點(diǎn)和1000條邊的圖，則該圖的鄰接矩陣有多少元素？10001000多少非零元素？若無(wú)向圖，則1000*2若有向圖，則1000該矩陣是否為稀疏矩陣？是3習(xí)題5-12設(shè)計(jì)算法，檢測(cè)采用鄰接表方法存儲(chǔ)、具有n個(gè)頂點(diǎn)的有向圖中是否存在從頂點(diǎn)v到頂點(diǎn)u的路徑。若存在路徑，算法給出信息true；否則給出信息false。思想：從一個(gè)頂點(diǎn)出發(fā)，遍歷整個(gè)

2、圖。廣度優(yōu)先遍歷：從頂點(diǎn)v出發(fā)，訪(fǎng)問(wèn)v的各個(gè)未訪(fǎng)問(wèn)的鄰接頂點(diǎn)，然后從這些鄰接頂點(diǎn)出發(fā)訪(fǎng)問(wèn)其他頂點(diǎn)。隊(duì)列存儲(chǔ)鄰接頂點(diǎn)輔助數(shù)組標(biāo)記各個(gè)頂點(diǎn)是否被訪(fǎng)問(wèn)4算法BFS (Head, v, visited. visited) BFS1初始化 CREATQ(Q). /*創(chuàng)建隊(duì)列 Q */ FOR i = 1 TO n DO visitedi 0. PRINT(v) . visitedv 1. Qv. /* 入隊(duì) */BFS2廣度優(yōu)先遍歷 WHILE NOT(ISEMTQ(Q) DO /* 當(dāng)隊(duì)列不空時(shí) */ ( v Q. /* 出隊(duì) */ p adjacent(Headv) . /* v的邊鏈表頭指針*/

3、WHILE p DO ( IF visitedVerAdj(p) = 0 THEN( Q VerAdj(p) . /* 入隊(duì) */ PRINT(VerAdj(p) ) . visitedVerAdj(p) 1. ) . p link(p). ) ) VerNameadjacentVerAdjcostlink頂點(diǎn)表中的結(jié)點(diǎn)邊鏈表中的結(jié)點(diǎn)5算法Find (Head, v, u. flag) Find1初始化 CREATQ(Q). /創(chuàng)建隊(duì)列 Q FOR i = 1 TO n DO visitedi 0. visitedv 1. flag false. Qv. /入隊(duì)Find2廣度優(yōu)先遍歷 WHIL

4、E NOT(ISEMTQ(Q) DO / 當(dāng)隊(duì)列不空時(shí) ( v Q. / 出隊(duì) p adjacent(Headv) . /v的邊鏈表頭指針6 WHILE p DO( IF(VerAdj(p)=u) THEN /找到u ( flag=true. RETURN. ) ELSE( IF( visitedVerAdj(p) = 0 )THEN( Q VerAdj(p) . /入隊(duì) visitedVerAdj(p) 1. ) ) p link(p). ) ) ) 7頂點(diǎn)之間是否存在路徑：從一個(gè)頂點(diǎn)出發(fā)，遍歷圖。習(xí)題5-13設(shè)G（V,E）是有向圖，請(qǐng)給出算法，判斷G中是否有回路，并要求算法的復(fù)雜性為O（n

5、+e）。拓?fù)渑判蚧静襟E： 從網(wǎng)中選擇一個(gè)入度為0的頂點(diǎn)且輸出之。 從網(wǎng)中刪除該頂點(diǎn)及其所有出邊。執(zhí)行 ，直至所有頂點(diǎn)已輸出，或網(wǎng)中剩余頂點(diǎn)入度均不為0 (說(shuō)明網(wǎng)中存在回路，無(wú)法繼續(xù)拓?fù)渑判?8建立一個(gè)數(shù)組count ，counti的元素值取對(duì)應(yīng)頂點(diǎn)i的入度；建立一個(gè)堆棧，棧中存放入度為0的頂點(diǎn)，每當(dāng)一個(gè)頂點(diǎn)的入度為0，就將其壓入棧。虛擬的堆棧利用變量top和count數(shù)組元素的值來(lái)模擬堆棧的壓入和彈出。top:“棧頂”位置，初始為-1counttop：次棧頂元素9Bool Graph : TopoOrder( ) int top = - 1 ;bool flag=false;for ( in

6、t i=0 ; in ; i + + ) if ( counti = = 0 ) counti = top ; top = i ; /入棧 for ( int i=0 ; in ; i + + ) /n個(gè)頂點(diǎn)，n次迭代 if ( top = = - 1 )/圖中有回路 flag=true; return flag; 10else int j=top ; top=counttop ; /出棧 / coutjVerAdj ; if ( -countk= = 0 ) countk=top ; top=k ; /入棧 p=p-link ; 115-14對(duì)于圖所示的非負(fù)有向網(wǎng)絡(luò)，給出Dijkstra算法

7、產(chǎn)生的由源點(diǎn)2到圖中其他頂點(diǎn)的最短路徑長(zhǎng)度及路徑所經(jīng)歷的頂點(diǎn)，寫(xiě)出生成過(guò)程。思想：圖中所有頂點(diǎn)分兩個(gè)集合；集合1包括已訪(fǎng)問(wèn)，確定了最短路徑的頂點(diǎn);集合2包括尚未確定最短路徑的頂點(diǎn)。按照最短路徑長(zhǎng)度遞增的順序逐個(gè)把2的頂點(diǎn)加到1中，直至從源點(diǎn)出發(fā)可以到達(dá)的所有頂點(diǎn)都包括到1中。12數(shù)組f, fi表示頂點(diǎn)i是否被訪(fǎng)問(wèn)。初始：0。數(shù)組dist, disti表示當(dāng)前找到的從源點(diǎn)s到頂點(diǎn)i 的最短路徑的長(zhǎng)度。初始：dists=0, 對(duì)其它頂點(diǎn)i，disti=+ 。數(shù)組path, pathi記錄s到i最短路徑中i的前驅(qū)頂點(diǎn)的編號(hào)。初始：-1。在未訪(fǎng)問(wèn)頂點(diǎn)中選擇dist值最小的頂點(diǎn)v，fv=1。依次考察v的

8、鄰接頂點(diǎn)w，若 distv+weight() distw ， 則distw = distv+weight()重復(fù) ，直至所有頂點(diǎn)被訪(fǎng)問(wèn)。131234250220410120515530335310415565320fpathdist0001-1000-1-1-1-1-1從頂點(diǎn)2開(kāi)始，更改f2和dist2141234250220410120515530335310415565320fpathdist0001-100010-12-12-115遍歷2的鄰接頂點(diǎn)3和4，更新151234250220410120515530335310415565320fpathdist0001-101010-12-12

9、-115選擇dist最小的頂點(diǎn)，且f值為0的頂點(diǎn)，即頂點(diǎn)3161234250220410120515530335310415565320fpathdist0001-101010-1232-11540遍歷頂點(diǎn)3的鄰接頂點(diǎn)5，(dist3+)dist5，更新171234250220410120515530335310415565320fpathdist0011-101010-1232-11540選擇dist最小，且f值為0的頂點(diǎn)，即頂點(diǎn)4，更新181234250220410120515530335310415565320fpathdist001140103510-1242-11530遍歷頂點(diǎn)4的鄰

10、接頂點(diǎn)1和5；(dist4+)=(15+20)dist1;(dist4+)=(15+15)dist5;191234250220410120515530335310415565320fpathdist001140113510-1242-11530dist最小的頂點(diǎn)5，更新f5=1；遍歷5的鄰居2和3，dist5+=(30+35)dist3=10201234250220410120515530335310415565320fpathdist101140113510-1242-11530dist最小的頂點(diǎn)1，更新f1=1；遍歷1的鄰居2和4，dist1+=(35+10)dist4=1521最短路徑

11、最短路徑長(zhǎng)度23 1024 15245 30241 3526 225-15：求圖中所有頂點(diǎn)之間的最短路徑思想：鄰接矩陣存儲(chǔ)圖，初始矩陣A(-1) ij = Edgeij；1.求A(0),即從vi到vj 經(jīng)由頂點(diǎn)是v0的最短路徑長(zhǎng)度;2.求A(1),即從vi到vj 經(jīng)由頂點(diǎn)是v0,v1的最短路徑長(zhǎng)度;n.求A(n-1),即從vi 到vj 經(jīng)由頂點(diǎn)是v0, v1,vn-1的最短路徑長(zhǎng)度；其中, A(k) ij = min A(k-1)ij，A(k-1)ik + A(k-1)kj , k = 0,1, n-1 23Aij 表示頂點(diǎn)i和j的最短路徑長(zhǎng)度；初始為鄰接矩陣值；pathij表示相應(yīng)路徑上頂點(diǎn)

12、j的前一個(gè)頂點(diǎn)的序號(hào)；初始時(shí)，若頂點(diǎn)之間有邊，則pathij=i，否則為-1。循環(huán)從k=0到n-1， 每次循環(huán)，更新Aij的值， 若(Aik + Akj) Aij, 則Aij= Aik + Akj)K=0時(shí)， i=1時(shí)，A10= ； i=2時(shí)，A20= 1； j=1時(shí)， A20+A01= 1+9= 10 A21= ， 更新A21=10 ； j=3時(shí)， A20+A03=1+3=4 A23= ， 更新 A23=4； i=3時(shí)，A30= ； k=1時(shí)， i=0時(shí)，A01=9； j=2時(shí), A01+A12= 9+5=14A32=4, 不變。 k=2時(shí)，i=0時(shí)，A02=14；j=1時(shí)，A21=10；A

13、01=9，不變； j=3時(shí)，A23=4；A03=3，不變； i=1時(shí)，A12=5；j=0時(shí)，A12+A20=（5+1） A10= ， 更新 A10=6 ； j=3時(shí)，A12+A23=（5+4） A13= ， 更新 A13=9 ； i=3時(shí)， A32=4；j=1時(shí)，A21=10；A31=2，不變； j=0時(shí)，A32+A20=（4+1）A30= ， 更新 A30=5； k=3時(shí)，i=0時(shí)，A03=3；j=1時(shí)，A03+A31=3+2=5A01=9 ， 更新 A01=5 ； j=2時(shí)， A03+A32= 3+4=7 A10=6 ，不變； j=2時(shí)， A13+A32= 9+4=13 A12=5，不變；

14、 i=2時(shí)，A23=4；j=0時(shí)，A23+A30=4+5=9 A20=1 ，不變； j=1時(shí)， A23+A31= 4+2=6 A21=10， 更新 A21=6。 5-16 prim算法29思想： 集合U=u0(u0V), E= ； 找到滿(mǎn)足 weight(u,v) min weight(u1,v1) | u1U, v1V-U, 的邊，把它并入E，同時(shí)v并入U(xiǎn)； 反復(fù)執(zhí)行 ,直至 V=U , 算法結(jié)束。從1頂點(diǎn)開(kāi)始 1 2 16 1 216 35 1 216 35 46 1 2 16 3 5 46 611 1 216 35 46 611 51830U=1，2V=3，4，5，6,123456165

15、1918106211133145-16 Kruskar算法思想：設(shè)最小支撐樹(shù)為T(mén)初始時(shí)有n個(gè)頂點(diǎn)，也就是n個(gè)連通分量。在E中選擇權(quán)值最小的邊，并將此邊從E中刪除。如果此邊的兩個(gè)頂點(diǎn)在不同的連通分量中，則將此邊加入到T中，從而導(dǎo)致T中減少一個(gè)連通分量;如果此邊的兩個(gè)頂點(diǎn)在同一連通分量中，則重復(fù)執(zhí)行 ，直至T中僅剩一個(gè)連通分量時(shí)，終止操作。 3 5 1 2 4 65 5 1 2 3 4 656 5 1 2 3 4 65611 5 1 2 3 4 6561116 5 1 2 3 4 656111618322，3，456112345616519106211133145-17 Kruskal算法的c+和

16、ADL實(shí)現(xiàn)尋找權(quán)值最小的邊；判斷兩個(gè)頂點(diǎn)是否在同一連通分量。思想：數(shù)組setn存儲(chǔ)各個(gè)頂點(diǎn)的分量標(biāo)識(shí)；初始：頂點(diǎn)在頂點(diǎn)表中的序號(hào)，之后每找到一條滿(mǎn)足條件的邊，將兩個(gè)頂點(diǎn)的標(biāo)識(shí)設(shè)為相同。Kruskal(edge,n,maxwt) /鄰接矩陣edge, 頂點(diǎn)個(gè)數(shù)n, 最大邊權(quán)值maxwtK1.初始化 FOR i=0 to n-1 DO seti=i. k0. minmaxwt. /k是邊個(gè)數(shù) 33K2.尋找 WHILE kn DO ( FOR i=0 to n-1 DO /尋找最小邊 ( FOR j=i+1 to n-1 DO ( IF edgeijmin THEN (minedgeij. a i

17、. b j ) ) ) min maxwt. edgeab maxwt. /從圖中刪除此邊 IF seta setb THEN ( kk+1. PRINT(a). PRINT(-). PRINT(b). PRINT( ). /輸出該邊 For i=0 to n DO /兩個(gè)頂點(diǎn)具有相同分量標(biāo)識(shí) ( IF seti=setb THEN (seta seti . RETURN) IF seti=seta THEN (setb seti . RETURN) ) ) 34習(xí)題5-19自由樹(shù)(即無(wú)環(huán)連通圖)T=的直徑是樹(shù)中所有頂點(diǎn)之間最短路徑的最大值。設(shè)計(jì)一個(gè)算法求T的直徑，分析算法的時(shí)間復(fù)雜度。分析：

18、對(duì)于每個(gè)頂點(diǎn)執(zhí)行一次Dijkstra算法，時(shí)間復(fù)雜度為O(n3)。對(duì)于無(wú)環(huán)連通圖，每對(duì)頂點(diǎn)之間存在唯一一條路徑，最大值是距離根最遠(yuǎn)的兩個(gè)葉子結(jié)點(diǎn)之間的距離。方法1：以每個(gè)度為1的頂點(diǎn)作起點(diǎn)，求到其他頂點(diǎn)的最短路徑長(zhǎng)度（深度優(yōu)先遍歷），找到最大值。在遍歷所有度為1的頂點(diǎn)之后，取最大值，即為樹(shù)的直徑.3536算法DFSg (Head, u .dist) /頂點(diǎn)u到i的距離DFS1初始化 CREATS(S) . S u. /*創(chuàng)建堆棧 S *將u壓入棧中 */ FOR i = 1 TO n DO (visitedi 0. disti -1.) distu=0.DFS2利用堆棧S深度優(yōu)先遍歷圖 WHI

19、LE NOT(ISEMPTY(S) DO /* 當(dāng)S不空時(shí) */( v S. /*彈出堆棧頂元素 */ IF visitedv = 0 THEN ( visitedv 1. p adjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p) = 0 THEN ( S VerAdj(p) . distVerAdj(p) distv+1.) p link(p). ) ) )算法diameter (Head)d1初始化 CREATS(S) . max 0. FOR i=0 to n DO ( IF counti=1 THEN S i). /*創(chuàng)建堆棧 S , 將

20、度為1的頂點(diǎn)壓入棧中 */d2深度優(yōu)先遍歷各個(gè)頂點(diǎn)，返回最大值 WHILE NOT(ISEMPTY(S) DO /* 當(dāng)S不空時(shí) */( v S. DFSg(Head, v. dist) FOR i=0 to n DO (IF distimax THEN (max disti.) )d3輸出 PRINT(max) RETURN. 時(shí)間復(fù)雜度：深度優(yōu)先遍歷是O(n+e)，對(duì)于鄰接表存儲(chǔ)結(jié)構(gòu)，遍歷次數(shù)不超過(guò)n次。37方法2的思想：用鄰接表作為存儲(chǔ)結(jié)構(gòu)依次刪去樹(shù)葉結(jié)點(diǎn)(度為1的頂點(diǎn))，將與其相連的頂點(diǎn)度數(shù)減1。第一輪刪去原樹(shù)T的所有樹(shù)葉后，所得樹(shù)為T(mén)1，再做第二輪刪除，即刪除T1的葉子，重復(fù)，若最后

21、剩下一個(gè)頂點(diǎn)，則樹(shù)直徑應(yīng)為刪除的輪數(shù)*2；若剩余兩個(gè)頂點(diǎn)，則直徑為刪除的輪數(shù)*2+1。38int diameter(int du, int n) int m; int r=0; / 當(dāng)前一輪的葉子個(gè)數(shù)，輪數(shù) do m=0; Queue q; for(int i=0;i2) for(int i=1; iverAdj; dus-; p=p-link; r+； while(m2); If(m=2) return 2*r+1; else return 2*r; 39時(shí)間復(fù)雜度分析：遍歷所有頂點(diǎn)，復(fù)雜度為o(n)習(xí)題5-20試修改prim算法，使之能在鄰接表存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)求圖的最小生成森林，并分析時(shí)間復(fù)

22、雜度。相當(dāng)于使用prim算法構(gòu)造多于一棵的樹(shù)，采用左孩子右兄弟結(jié)構(gòu)存儲(chǔ)。1.從任意指定的一個(gè)頂點(diǎn)u開(kāi)始，使其成為第一棵樹(shù)的根結(jié)點(diǎn)，用prim算法找到連接u的權(quán)值最小的邊，將另一頂點(diǎn)v作為u的孩子結(jié)點(diǎn)，重復(fù)操作，生成第一棵樹(shù)；2.從剩余邊中找到權(quán)值最小的邊，使其中一個(gè)頂點(diǎn)成為新樹(shù)的根，并作為上一棵樹(shù)的兄弟結(jié)點(diǎn)，重復(fù)，生成所有樹(shù)。40Void forest-prim(int k, Tree& T) struct int vex; int cost; closedgen; /頂點(diǎn)和權(quán)值，n為圖中頂點(diǎn)個(gè)數(shù) Edge *p; closedgek.cost=0; for(int j=0;jlink) if

23、( p-veradj =k) closedgej.cost=p-cost; for(int i=1;in;i+) int min=10000; for( int j=0;jn;j+) /找權(quán)值最小的邊 if (closedgej.costmin & closedgej.cost!=0) min=closedgej.cost; k=j; if(closedgek.costlink) if(p-cost Veradj.cost) /更新鄰接頂點(diǎn)closedge closedgep-Veradj.vex=k; closedgep-Veradj.cost=p-cost; else forest-pri

24、m(k,T); /處理下一個(gè)連通分量 42voidAddto (Tree&T,inti,intj) /把邊(i,j)添加到樹(shù)T中 TreeNode*p, *q, *r； p=find(T,i);/找到頂點(diǎn)i對(duì)應(yīng)的指針p q-data=j; if(!p) /起始頂點(diǎn)不屬于森林中已有的任何一棵樹(shù) p-data=i; for(r=T.root ;r-nextBrother ;r=r-nexBrother); r-nextBrother=p; p-firstchild=q; /作為新樹(shù)插入到最右側(cè) elseif(!p-firstchild) /還沒(méi)有孩子結(jié)點(diǎn) p-firstchild=q;/作為第一個(gè)

25、孩子結(jié)點(diǎn) else/屬于某一存在的樹(shù)，且已經(jīng)有了孩子結(jié)點(diǎn) for(r=p-firstchild;r-nexBrother;r=r-nextBrother); r-nextBrother=q;/作為最后一個(gè)孩子的兄弟 43如果在有向無(wú)環(huán)的帶權(quán)圖中 用有向邊表示一個(gè)工程中的各項(xiàng)活動(dòng)(Activity) 用邊上的權(quán)值表示活動(dòng)的持續(xù)時(shí)間(Duration) 用頂點(diǎn)表示事件(Event)則這樣的有向圖叫做用邊表示活動(dòng)的網(wǎng)絡(luò)，簡(jiǎn)稱(chēng)AOE (Activity On Edges)網(wǎng)絡(luò)。方法：求網(wǎng)中所有事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間；再分別求所有活動(dòng)的最早開(kāi)始和最晚開(kāi)始時(shí)間；最早和最晚時(shí)間相同的活動(dòng)為關(guān)鍵活動(dòng)

26、；關(guān)鍵活動(dòng)組成了關(guān)鍵路徑。44練習(xí)：求AOE網(wǎng)的關(guān)鍵路徑事件vj的最早發(fā)生時(shí)間ve(j): maxve(i)+ weight(i , j) E(G); k = 2, 3, , n ve(1)=0;事件vj的最遲發(fā)生時(shí)間vl(j): minvl(k)- weight(j , k) E(G), j= n-1, n-2, , 1 vl(n)=ve(n);設(shè)活動(dòng)ai在有向邊上， 則ai的最早開(kāi)始時(shí)間e(i)=ve(j)； 最遲開(kāi)始時(shí)間l(i)= vl(k)-weight()。4546CFBDAE 3431 22匯點(diǎn)源點(diǎn)11首先，進(jìn)行拓?fù)渑判?；之后，?jì)算事件時(shí)間；再計(jì)算活動(dòng)時(shí)間；找到關(guān)鍵活動(dòng)，形成關(guān)鍵路

27、徑。實(shí)驗(yàn)題1假設(shè)用鏈表表示集合，要求寫(xiě)一個(gè)函數(shù)Intersection，其功能是求兩個(gè)用鏈表表示的集合的交集。集合鏈表p和q的交集求法： 從前向后掃描p的每個(gè)節(jié)點(diǎn)，如果該節(jié)點(diǎn)在q中，則該節(jié)點(diǎn)是交集的一個(gè)元素，將該節(jié)點(diǎn)插入鏈表r。bool inlist(int t, SLNode* p) /元素t是否在鏈表p中 SLNode*temp; for(temp=p-next ;temp!=0;temp=temp-next) if(temp-data=t) return true; return false; 47SLNode* Intersection(SLNode *p, SLNode *q) /求交集SLNode* r=new SLNode();SLNode* t=r;