圖結(jié)構(gòu)習(xí)題答案

1、.第6章 圖【例6-1】回答下列問(wèn)題：（1）具有n個(gè)頂點(diǎn)的連通圖至少有多少條邊?（2）具有n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有多少條邊?這樣的圖應(yīng)該是什么形狀?（3）具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖最多有多少條邊?解： （1）具有n個(gè)頂點(diǎn)的連通圖至少有n-1條邊。這是一個(gè)與生成樹(shù)相關(guān)的問(wèn)題。生成樹(shù)是一個(gè)連通圖，它具有能夠連通圖中任何兩個(gè)頂點(diǎn)的最小邊集，任何一個(gè)生成樹(shù)都具有n-1邊。因此，具有n個(gè)頂點(diǎn)的連通圖至少有n-1條邊。（2）具有n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有n條邊，這樣的圖是一個(gè)由n個(gè)頂點(diǎn)構(gòu)成的環(huán)。強(qiáng)連通圖是相對(duì)于有向圖而言的。由于強(qiáng)連通圖要求圖中任何兩個(gè)頂點(diǎn)之間能夠相互連通，因此每個(gè)頂點(diǎn)至少要有一條以該頂點(diǎn)為弧

2、頭的弧和一條以該頂點(diǎn)為弧尾的弧，每個(gè)頂點(diǎn)的入度和出度至少各為1，即頂點(diǎn)的度至少為2，這樣根據(jù)圖的頂點(diǎn)數(shù)、邊數(shù)以及各項(xiàng)點(diǎn)的度三者之間的關(guān)系計(jì)算可得：邊數(shù)=2n/2=n。（3）具有n個(gè)頂點(diǎn)的有向無(wú)環(huán)圖最多有n(n1)/2條邊。這是一個(gè)拓?fù)渑判蛳嚓P(guān)的問(wèn)題。個(gè)有向無(wú)環(huán)圖至少可以排出一個(gè)拓?fù)湫蛄?，不妨設(shè)這n個(gè)頂點(diǎn)排成的拓?fù)湫蛄袨関1，v2，v3，vn，那么在這個(gè)序列中，每個(gè)頂點(diǎn)vi只可能與排在它后面的頂點(diǎn)之間存在著以vi為弧尾的弧，最多有n-i條，因此在整個(gè)圖中最多有(n-1)+(n-2)+ +2+1=n(n-1)/2條邊。2圖的存儲(chǔ)結(jié)構(gòu)常用的存儲(chǔ)結(jié)構(gòu)有鄰接矩陣和鄰接表。（1）鄰接矩陣表示法設(shè)G(V，E

3、)是有n(n1)個(gè)頂點(diǎn)的圖。則G的鄰接矩陣是按如下定義的n階方陣：0其它1當(dāng)（i,Vj）E或E時(shí)costi,j= 0 1 1 01 0 1 11 1 0 10 1 1 0A2=A1=0 1 10 0 10 0 0 例如，圖6-1中G1，2的鄰接矩陣分別表示為A1、A2，矩陣的行列號(hào)對(duì)應(yīng)于圖6-1中結(jié)點(diǎn)的序號(hào)。由鄰接矩陣的定義可知，無(wú)向圖的鄰接矩陣必定是對(duì)稱陣；有向圖的鄰接矩陣不一定是對(duì)稱的。 根據(jù)鄰接矩陣，很容易判定任意兩個(gè)頂點(diǎn)之間是否有邊相連。求各頂點(diǎn)的度也是非常容易的。對(duì)于無(wú)向圖，頂點(diǎn)Vi的度就是鄰接矩陣中第i行(或第j列)上非零元的個(gè)數(shù)，即。對(duì)于有向圖，第i行中非零元的個(gè)數(shù)為頂點(diǎn)Vi的出

4、度，而第i列上的非零元個(gè)數(shù)為頂點(diǎn)Vi的入度。（2）鄰接表表示法圖的鄰接鏈表存儲(chǔ)結(jié)構(gòu)是一種順序分配和鏈?zhǔn)椒峙湎嘟Y(jié)合的存儲(chǔ)結(jié)構(gòu)括兩個(gè)部分：一部分是向量，另一部分是鏈表。鄰接鏈表中的表頭部分是向量，用來(lái)存儲(chǔ)n個(gè)表頭結(jié)點(diǎn)。向量的下標(biāo)指示頂點(diǎn)的序號(hào)。例如，對(duì)于圖6-1中G1和G2，其鄰接鏈表如圖6-3所示。在無(wú)向圖的鄰接表中頂點(diǎn)vi的度就是第i個(gè)鏈表中結(jié)點(diǎn)的個(gè)數(shù)。在有向圖中，第i個(gè)鏈表的結(jié)點(diǎn)數(shù)僅是vi的出度，求vi的入度，必須查遍n個(gè)鏈表才能得出。(a) G1的鄰接表123332(b) G2的鄰接表圖6-3 鄰接表31234124433221【例6-2】 圖G(V，E)，其中V=1,2,3,4,5,6，

5、,，請(qǐng)畫出圖G，并寫出其鄰接矩陣和鄰接表表示。解：圖G如圖6-4中的(a)所示，圖G的鄰接矩陣和鄰接表表示分別如圖(b)和(c)所示。對(duì)于這類問(wèn)題，只要掌握了圖的概念和存儲(chǔ)結(jié)構(gòu)就可以做出正確的答案。通常情況下對(duì)圖的頂點(diǎn)排列順序和各頂點(diǎn)的鄰接點(diǎn)排列順序并沒(méi)有特定要求，因此，在寫出鄰接矩陣和鄰接表表示時(shí)，只要按照某種排列順序畫出相應(yīng)的結(jié)構(gòu)圖就可以了。但應(yīng)該注意的是，對(duì)于鄰接矩陣表示，如果頂點(diǎn)結(jié)點(diǎn)的順序不同，那么鄰接矩陣就不相同；對(duì)于鄰接表表示，如果頂點(diǎn)結(jié)點(diǎn)的順序或者鄰接點(diǎn)的順序不同，那么鄰接表就不相同。0 1 1 1 0 00 0 0 0 1 00 1 0 0 1 10 0 0 0 0 10 0

6、0 0 1 10 0 0 0 0 0(b)圖6-4 圖及其存儲(chǔ)結(jié)構(gòu)1(a)34256(c)126453223545666【例6-3】已知一個(gè)無(wú)向圖的鄰接表如圖6-5所示，要求：（1）畫出該無(wú)向圖；（2）根據(jù)鄰接表，分別寫出用DFS(深度優(yōu)先搜索)和BFS（廣度優(yōu)先搜索）算法從頂點(diǎn)V0開(kāi)始遍歷該圖后所得到的遍歷序列。圖6-5 圖的鄰接表存儲(chǔ)V6V0V1V5V3V4V22305604361121210250634解：（1）該無(wú)向圖如圖6-6所示。v0v1v2v3v4v6v5圖6-6 無(wú)向圖（2）根據(jù)該無(wú)向圖的鄰接表表示，從頂點(diǎn)V0開(kāi)始的深度優(yōu)先遍歷序列為：V0、V2、V3、V1、V4、V6、V5。

7、廣度優(yōu)先遍歷序列為V0、V2、V5、V6、V1、V3、V4。從圖的邏輯結(jié)構(gòu)上來(lái)講，從圖中某個(gè)頂點(diǎn)開(kāi)始的深度(或廣度)優(yōu)先遍歷序列不一定是唯一的。這是因?yàn)樵谶壿嫿Y(jié)構(gòu)中，并沒(méi)有對(duì)每個(gè)頂點(diǎn)的所有鄰接點(diǎn)規(guī)定它們之間的先后順序，這樣在搜索算法中選取第個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)時(shí)可能會(huì)有不同的結(jié)果。但是在存儲(chǔ)結(jié)構(gòu)中，明確地給出了鄰接點(diǎn)的先后順序，這時(shí)深度優(yōu)先和廣度優(yōu)先遍歷序列就是唯一的?！纠?-4】對(duì)于如圖6-8所示的帶權(quán)無(wú)向圖，用圖示說(shuō)明：（1）利用Prim算法從頂點(diǎn)a開(kāi)始構(gòu)造最小生成樹(shù)的過(guò)程；3e1fdcbag97946218548圖6-8 帶權(quán)無(wú)向圖（2）利用Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程；解：

8、（1）利用Prim算法從頂點(diǎn)a開(kāi)始構(gòu)造最小生成樹(shù)的過(guò)程如圖6-9所示。aefdcbg初始狀態(tài)aefdcbg連通e2aefdcbg連通g21aefdcbg連通d2133aefdcbg連通f2143aefdcbg連通b2146圖6-9 用Prim算法構(gòu)造最小生成樹(shù)的過(guò)程3aefdcbg連通c21461（2）利用Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程如圖6-10所示。aefdcbg初始狀態(tài)aefdcbg增加第2條邊11aefdcbg增加第1條邊13aefdcbg增加第5條邊21413aefdcbg增加第4條邊211aefdcbg增加第3條邊211圖6-10 用Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程3

9、aefdcbg增加第6條邊21461【例6-5】 一個(gè)帶權(quán)無(wú)向圖的最小生成樹(shù)是否一定唯一？在什么情況下構(gòu)造出的最小生成樹(shù)可能不唯一？解：一個(gè)帶權(quán)無(wú)向圖的最小生成樹(shù)不一定是唯一的。從Kruskal算法構(gòu)造最小生成樹(shù)的過(guò)程可以看出，當(dāng)從圖中選擇當(dāng)前權(quán)值最小的邊時(shí)，如果存在多條這樣的邊，并且這些邊與已經(jīng)選取的邊構(gòu)成回路，此時(shí)這些邊就不可能同時(shí)出現(xiàn)在一棵最小生成樹(shù)中，對(duì)這些邊的不同選擇結(jié)果可能會(huì)產(chǎn)生不同的最小生成樹(shù)。習(xí)題6一、單項(xiàng)選擇題 1. 在一個(gè)具有n個(gè)頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的入度數(shù)之和為(1. A )。A. sB. s-1C. s+1D. n 2. 在一個(gè)具有n個(gè)

10、頂點(diǎn)的有向圖中，若所有頂點(diǎn)的出度數(shù)之和為s，則所有頂點(diǎn)的度數(shù)之和為(2. D)。A. s B. s-1C. s+1D. 2s 3. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，若具有e條邊，則所有頂點(diǎn)的度數(shù)之和為(3. D )。A. n B. eC. n+eD. 2e 4. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，所含的邊數(shù)為(4. C)。A. nB. n(n-1)C. n(n-1)/2D. n(n+1)/2 5. 在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，所含的邊數(shù)為( 5. B )。A. n B. n(n-1) C. n(n-1)/2 D. n(n+1)/2 6. 在一個(gè)無(wú)向圖中，若兩頂點(diǎn)之間的路徑長(zhǎng)度為k，則該路徑

11、上的頂點(diǎn)數(shù)為( 6. B )。A. k B. k+1 C. k+2 D. 2k 7. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向連通圖，它包含的連通分量的個(gè)數(shù)為(7. B)。A. 0 B. 1 C. n D. n+1 8. 若一個(gè)圖中包含有k個(gè)連通分量，若要按照深度優(yōu)先搜索的方法訪問(wèn)所有頂點(diǎn)，則必須調(diào)用(8. A )次深度優(yōu)先搜索遍歷的算法。A. k B. 1 C. k-1 D. k+1 9. 若要把n個(gè)頂點(diǎn)連接為一個(gè)連通圖，則至少需要(9. C )條邊。A. n B. n+1 C. n-1 D. 2n 10. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接矩陣中，表示邊存在的元素（又稱為有效元素）的個(gè)數(shù)為( 10

12、. D )。A. n B. ne C. e D. 2e 11. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個(gè)數(shù)為( 11. C )。A. n B. ne C. e D. 2e 12. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖的鄰接表中，邊結(jié)點(diǎn)的個(gè)數(shù)為(12. D )。A. n B. ne C. e D. 2e 13. 在一個(gè)具有n個(gè)頂點(diǎn)和e條邊的有向圖的鄰接表中，保存頂點(diǎn)單鏈表的表頭指針向量的大小至少為(13. A )。A. n B. 2n C. e D. 2e 14. 在一個(gè)無(wú)權(quán)圖的鄰接表表示中，每個(gè)邊結(jié)點(diǎn)至少包含(14. B )域。A. 1 B. 2 C. 3 D. 4 1

13、5. 對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為(15. B )。A. k1 B. k2 C. k1-k2 D. k1+k2 16. 對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度為k1，出度為k2，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)為(16. C )。A. k1 B. k2 C. k1-k2 D. k1+k2 17. 對(duì)于一個(gè)無(wú)向圖，下面(17. A )種說(shuō)法是正確的。A. 每個(gè)頂點(diǎn)的入度等于出度 B. 每個(gè)頂點(diǎn)的度等于其入度與出度之和C. 每個(gè)頂點(diǎn)的入度為0 D. 每個(gè)頂點(diǎn)的出度為0 18. 在一個(gè)有向圖的鄰接表中，每個(gè)頂點(diǎn)單鏈表中結(jié)點(diǎn)的個(gè)數(shù)等于該頂點(diǎn)

14、的(18. A)。A. 出邊數(shù) B. 入邊數(shù) C. 度數(shù) D. 度數(shù)減1 19. 若一個(gè)圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點(diǎn)A開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( 19. B )。A. A,B,C,F,D,E B. A,C,F,D,E,BC. A,B,D,C,F,E D. A,B,D,F,E,C 20. 若一個(gè)圖的邊集為(A,B),(A,C),(B,D),(C,F),(D,E),(D,F)，則從頂點(diǎn)A開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為(20. D )。A. A,B,C,D,E,F B. A,B,C,F,D,EC.

15、 A,B,D,C,E,F D. A,C,B,F,D,E 21. 若一個(gè)圖的邊集為,，則從頂點(diǎn)1開(kāi)始對(duì)該圖進(jìn)行深度優(yōu)先搜索，得到的頂點(diǎn)序列可能為(21. A )。A. 1,2,5,4,3 B. 1,2,3,4,5C. 1,2,5,3,4 D. 1,4,3,2,5 22. 若一個(gè)圖的邊集為,，則從頂點(diǎn)1開(kāi)始對(duì)該圖進(jìn)行廣度優(yōu)先搜索，得到的頂點(diǎn)序列可能為( 22. C )。A. 1,2,3,4,5 B. 1,2,4,3,5C. 1,2,4,5,3 D. 1,4,2,5,3 23. 由一個(gè)具有n個(gè)頂點(diǎn)的連通圖生成的最小生成樹(shù)中，具有(23. B )條邊。A. n B. n-1 C. n+1 D. 2n

16、24. 已知一個(gè)有向圖的邊集為,，則由該圖產(chǎn)生的一種可能的拓?fù)湫蛄袨?24. A )。A. a,b,c,d,e B. a,b,d,e,b C. a,c,b,e,d D. a,c,d,b,e二、填空題 1. 在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的_倍。1. 2 2. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向完全圖中，包含有_條邊，在一個(gè)具有n個(gè)頂點(diǎn)的有向完全圖中，包含有_條邊。 2. n(n-1)/2，n(n-1) 3. 假定一個(gè)有向圖的頂點(diǎn)集為a,b,c,d,e,f，邊集為, , , , , ，則出度為0的頂點(diǎn)個(gè)數(shù)為_(kāi)，入度為1的頂點(diǎn)個(gè)數(shù)為_(kāi)。3. 2，4 4. 在一個(gè)具有n個(gè)頂點(diǎn)的無(wú)向圖中，要連通所有

17、頂點(diǎn)則至少需要_條邊。4. n-1 5. 表示圖的兩種存儲(chǔ)結(jié)構(gòu)為_(kāi)和_。5. 鄰接矩陣，鄰接表 6. 在一個(gè)連通圖中存在著_個(gè)連通分量。6. 1 7. 圖中的一條路徑長(zhǎng)度為k，該路徑所含的頂點(diǎn)數(shù)為_(kāi)。7. k+1 8. 若一個(gè)圖的頂點(diǎn)集為a,b,c,d,e,f，邊集為(a,b),(a,c),(b,c),(d,e)，則該圖含有_個(gè)連通分量。 8. 3 9. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的圖，若采用鄰接矩陣表示，則矩陣大小至少為_(kāi)。9. n，n 10. 對(duì)于具有n個(gè)頂點(diǎn)和e條邊的有向圖和無(wú)向圖，在它們對(duì)應(yīng)的鄰接表中，所含邊結(jié)點(diǎn)的個(gè)數(shù)分別為_(kāi)和_。10. 2e，e 11. 在有向圖的鄰接表和逆鄰接表表示中，

18、每個(gè)頂點(diǎn)鄰接表分別鏈接著該頂點(diǎn)的所有_和_結(jié)點(diǎn)。11. 出邊，入邊 12. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時(shí)，求任一頂點(diǎn)度數(shù)的時(shí)間復(fù)雜度分別為_(kāi)和_。 12. O（n），O（e/n） 13. 假定一個(gè)圖具有n個(gè)頂點(diǎn)和e條邊，則采用鄰接矩陣和鄰接表表示時(shí)，其相應(yīng)的空間復(fù)雜度分別為_(kāi)和_。13.O（n2），O（n+e） 14. 一個(gè)圖的邊集為(a,c),(a,e),(b,e),(c,d),(d,e)，從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為_(kāi)，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為_(kāi)。 14. acdeb，acedb （答案不唯一） 15.

19、一個(gè)圖的邊集為,，從頂點(diǎn)a出發(fā)進(jìn)行深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為_(kāi)，從頂點(diǎn)a出發(fā)進(jìn)行廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列為_(kāi)。15. acfebd，acefbd （答案不唯一） 16. 圖的_優(yōu)先搜索遍歷算法是一種遞歸算法，圖的_優(yōu)先搜索遍歷算法需要使用隊(duì)列。16. 深度，廣度 17. 對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖，其生成樹(shù)中的頂點(diǎn)數(shù)和邊數(shù)分別為_(kāi)和_。17. n，n-1 18. 若一個(gè)連通圖中每個(gè)邊上的權(quán)值均不同，則得到的最小生成樹(shù)是_（唯一/不唯一）的。18. 唯一 19. 根據(jù)圖的存儲(chǔ)結(jié)構(gòu)進(jìn)行某種次序的遍歷，得到的頂點(diǎn)序列是_（唯一/不唯一）的。19. 唯一 20. 假定一個(gè)有向圖的

20、邊集為,，對(duì)該圖進(jìn)行拓?fù)渑判虻玫降捻旤c(diǎn)序列為_(kāi)。 20. aebdcf（答案不唯一）三、應(yīng)用題1. 對(duì)于一個(gè)無(wú)向圖6-11(a)，假定采用鄰接矩陣表示，試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。注：每一種序列都是唯一的，因?yàn)槎际窃诖鎯?chǔ)結(jié)構(gòu)上得到的。1. 深度優(yōu)先搜索序列：0,1,2,8,3,4,5,6,7,9 廣度優(yōu)先搜索序列：0,1,4,2,7,3,8,6,5,9 2. 對(duì)于一個(gè)有向圖6-11(b)，假定采用鄰接表表示，并且假定每個(gè)頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)是按出邊鄰接點(diǎn)序號(hào)從大到小的次序鏈接的，試分別寫出從頂點(diǎn)0出發(fā)按深度優(yōu)先搜索遍歷得到的頂點(diǎn)序列

21、和按廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。 注：每一種序列都是唯一的，因?yàn)槎际窃诖鎯?chǔ)結(jié)構(gòu)上得到的。 圖6-110165948372(a)603451278(b)2. 深度優(yōu)先搜索序列：0,4,7,5,8,3,6,1,2 廣度優(yōu)先搜索序列：0,4,3,1,7,5,6,2,83. 已知一個(gè)無(wú)向圖的鄰接矩陣如圖6-12(a)所示，試寫出從頂點(diǎn)0出發(fā)分別進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)序列。3. 深度優(yōu)先搜索序列：0,2,3,5,6,1,4 廣度優(yōu)先搜索序列：0,2,3,5,6,1,4 4. 已知一個(gè)無(wú)向圖的鄰接表如圖6-12(b)所示，試寫出從頂點(diǎn)0出發(fā)分別進(jìn)行深度優(yōu)先和廣度優(yōu)先搜索遍歷得到的頂點(diǎn)

22、序列。(a) (b)圖6-124. 深度優(yōu)先搜索序列：0,3,6,4,1,5,2 廣度優(yōu)先搜索序列：0,3,2,6,5,4,15. 已知圖6-13所示的一個(gè)網(wǎng)，按照Prim方法，從頂點(diǎn)1 出發(fā)，求該網(wǎng)的最小生成樹(shù)的產(chǎn)生過(guò)程。 (a)V1V2V3V4V5V6V760506540457050524230V1V2V3V4V5V6V750(c)V1V2V3V4V5V6V7(b)5. 過(guò)程如圖6-16所示 V1V2V3V4V5V6V7504045504230(h)圖6-16V1V2V3V4V5V6V75040504230(g)V1V2V3V4V5V6V750405030(f)V1V2V3V4V5V6V7

23、5040(d)V1V2V3V4V5V6V7504050(e)6. 已知圖6-13所示的一個(gè)網(wǎng)，按照Kruskal方法，求該網(wǎng)的最小生成樹(shù)的產(chǎn)生過(guò)程。圖6-13V1V2V3V4V5V6V7605065404570505242306. 求解過(guò)程如圖6-17所示。V1V2V3V4V5V6V7(a)30V1V2V3V4V5V6V7(b)3040V1V2V3V4V5V6V7(c)304042圖6-17V1V2V3V4V5V6V7(e)3040424550V1V2V3V4V5V6V7(f)304042455050V1V2V3V4V5V6V7(d)304042457. 圖6-14所示為一個(gè)有向網(wǎng)圖及其帶權(quán)鄰

24、接矩陣，要求對(duì)有向圖采用Dijkstra算法，求從V0 到其余各頂點(diǎn)的最短路徑。(a) 有向帶權(quán)圖 V1V0V5V4V3V25106030100502010 10 30 100 5 50 10 20 60 (b) 帶權(quán)鄰接矩陣圖6-14 有向帶權(quán)圖及其鄰接矩陣7. 求解過(guò)程如下表所示。終點(diǎn) 從v0到各終點(diǎn)的D值和最短路徑的求解過(guò)程 i=1 i=2 i=3 i=4 i=5 V1 無(wú) V2 10 (v0,v2) V3 60 (v0,v2,v3) 50 (v0,v4,v3) V4 30 (v0,v4) 30 (v0,v4) V5 100 (v0,v5) 100 (v0,v5) 90 (v0,v4,v

25、5) 60 (v0,v4,v3,v5) Vj V2 V4 V3 V5 S v0,v2 v0,v2,v4v0,v2,v3,v4v0,v2,v3,v4,v58. 圖6-15給出了一個(gè)具有15個(gè)活動(dòng)、11個(gè)事件的工程的AOE網(wǎng)，求關(guān)鍵路徑。v1v5v3v8v11v9v1001a2=4a5=3a9=4a13=10a14=1a15=6v6v7v4v2圖6-15a1=3a3=2a4=1a7=6a8=8a11=7a12=4a6=5a10=28. 求解過(guò)程如下：事件的最早發(fā)生時(shí)間vek。 ve (1)=0 ve (2)=3 ve (3)=4 ve (4)=ve(2)+2=5 ve (5)=maxve(2)+1

26、,ve(3)+3=7 ve (6)=ve(3)+5=9 ve (7)=maxve(4)+6,ve(5)+8=15 ve (8)=ve(5)+4=11 ve (9)=maxve(8)+10,ve(6)+2=21 ve (10)=maxve(8)+4,ve(9)+1=22 ve (11)=maxve(7)+7,ve(10)+6=28事件的最遲發(fā)生時(shí)間vlk。 vl (11)= ve (11)=28 vl (10)= vl (11)-6=22 vl (9)= vl (10)-1=21 vl (8)=min vl (10)-4, vl (9)-10=11 vl (7)= vl (11)-7=21 vl

27、 (6)= vl (9)-2=19 vl (5)=min vl (7)-8,vl (8)-4=7 vl (4)= vl (7)-6=15 vl (3)=min vl (5)-3, vl (6)-5=4 vl (2)=min vl (4)-2, vl (5)-1=6 vl (1)=minvl (2)-3, vl (3)-4=0活動(dòng)ai的最早開(kāi)始時(shí)間ei和最晚開(kāi)始時(shí)間li。 活動(dòng)a1 e (1)=ve (1)=0 l (1)=vl (2) -3 =3 活動(dòng)a2 e (2)=ve (1)=0 l (2)=vl (3) - 4=0 活動(dòng)a3 e (3)=ve (2)=3 l (3)=vl (4) -

28、2=13 活動(dòng)a4 e (4)=ve (2)=3 l (4)=vl (5) - 1=6 活動(dòng)a5 e (5)=ve (3)=4 l (5)=vl (5) - 3=4 活動(dòng)a6 e (6)=ve (3)=4 l (6)=vl (6) - 5=14 活動(dòng)a7 e (7)=ve (4)=5 l (7)=vl (7) - 6=15 活動(dòng)a8 e (8)=ve (5)=7 l (8)=vl (7) - 8=13 活動(dòng)a9 e (9)=ve (5)=7 l (9)=vl (8) - 4=7 活動(dòng)a10 e (10)=ve (6)=9 l (10)=vl (9) - 2=19 活動(dòng)a11 e (11)=ve (7)=15 l (11)=vl (11) - 7=21 活動(dòng)a12 e (12)=ve (8)=11 l (12)=vl (10) - 4=18 活動(dòng)a13 e (13)=ve (8)=11 l (13)=vl (9) - 10=11 活動(dòng)a14 e (14)=ve (9)=21 l (14)=vl (10) -