習(xí)題五(參考答案)

1、1. 設(shè)一有向圖G=(V,E)，其中V=a,b,c,d,e ， E=<a,b>, <a,d>, <b,a>, <c,b>, <c,d>, <d,e>,<e,a>, <e,b>, <e,c> 請畫出該有向圖，并求各頂點的入度和出度。 分別畫出有向圖的正鄰接鏈表和逆鄰接鏈表。 寫出相應(yīng)的鄰接矩陣表示。 寫出從頂點a開始的深度優(yōu)先和廣度優(yōu)先遍歷序列。 畫出從頂點a開始的深度優(yōu)先和廣度優(yōu)先生成樹。A: 入度2 出度2B: 入度3 出度1C：入度1出度2D:入度2 出度1E:入度1 出度3總計 入

2、度9 ；出度9 a b c d e a 0 1 0 1 0 b 1 0 0 0 0c 0 1 0 1 0d 0 0 0 0 1e 1 1 1 0 0從a點開始深度優(yōu)先序列 a->b->d->e->c 廣度優(yōu)先遍歷序列: a->b->d->e->c （a） 深度優(yōu)先生成樹 （b）廣度優(yōu)先生成樹2. 對于圖7-27所示的帶權(quán)無向圖。 按照Prime算法給出從頂點2開始構(gòu)造最小生成樹的過程。 按照Kruskal算法給出最小生成樹的過程。 3. 一個AOV網(wǎng)用鄰接矩陣表示，如圖7-31。用拓撲排序求該AOV網(wǎng)的一個拓撲序列，給出相應(yīng)的步驟。(提示: 先根

3、據(jù)鄰接矩陣畫出有向圖,然后寫出可能的一個拓撲序列) 相關(guān)知識:AOV網(wǎng): 圖中頂點表示活動，有向邊表示活動之間的優(yōu)先關(guān)系，這樣的有向圖稱為頂點表示活動的網(wǎng)(Activity On Vertex Network ，AOV網(wǎng)) 。 有向圖的拓撲排序：構(gòu)造AOV網(wǎng)中頂點的一個拓撲線性序列(v1,v2, ,vn)，使得該線性序列不僅保持原來有向圖中頂點之間的優(yōu)先關(guān)系，而且對原圖中沒有優(yōu)先關(guān)系的頂點之間也建立一種(人為的)優(yōu)先關(guān)系。算法思想: 在AOV網(wǎng)中選擇一個沒有前驅(qū)的頂點且輸出； 在AOV網(wǎng)中刪除該頂點以及從該頂點出發(fā)的(以該頂點為尾的弧)所有有向弧(邊) ； 重復(fù)、，直到圖中全部頂點都已輸出(圖

4、中無環(huán))或圖中不存在無前驅(qū)的頂點(圖中必有環(huán))。V0-v1,v0-v2V1-v3,v1-v4,v1-v5V2-v4,v2-v6V4-v6V5-v6入度為零,可畫圖 V0-v1-v3-v5-v2-v4-v64. 假設(shè)一個工程的進度計劃用AOE網(wǎng)表示，如圖7-33所示。 求出每個事件的最早發(fā)生時間和最晚發(fā)生時間。 該工程完工至少需要多少時間? 求出所有關(guān)鍵路徑和關(guān)鍵活動。相關(guān)知識：與AOV網(wǎng)相對應(yīng)的是AOE(Activity On Edge) ，是邊表示活動的有向無環(huán)圖，圖中頂點表示事件(Event)，每個事件表示在其前的所有活動已經(jīng)完成，其后的活動可以開始；弧表示活動，弧上的權(quán)值表示相應(yīng)活動所需

5、的時間或費用。5. 已知帶權(quán)有向圖如圖7-29所示，請利用迪杰斯特拉(Dijkstra) 算法從頂點V4出發(fā)到其余頂點的最短路徑及長度，給出相應(yīng)的求解步驟。 令S=Vs ，用帶權(quán)的鄰接矩陣表示有向圖，對圖中每個頂點Vi按以下原則置初值： 選擇一個頂點Vj ，使得：distj=Min distk| VkV-S Vj就是求得的下一條最短路徑終點，將Vj 并入到S中，即S=SVj 。 對V-S中的每個頂點Vk ，修改distk，方法是：若distj+Wjk<distk，則修改為：distk=distj+Wjk ("VkV-S ) 重復(fù)，直到S=V為止?；蛘卟捎靡韵路绞剑航K點i=1i=2i=3i=4i=5v130 (v4,v2,v1)30 (v4,v2,v1)v220 (v4,v2)20 (v4,v2)v345 (v4,v2,v1,v3)45 (v4,v2,v1,v3)v550 (v4,v2,v5)50 (v4,v2,v5)50 (v4,v2,v5)50 (v4,v2,v5)v615 (v4,v6)vjV6V2V1V3V5Sv4,v6v4,v6,v2v4,v6,v