最新習(xí)題五資料

1、1. 設(shè)一有向圖 G=(V,E,其中 V=a,b,c,d,e , E=va,b, va,d, vb,a, vc,b, vc,d, vd,e,ve,a.ve,b, ve,c 請(qǐng)畫出該有向圖，并求各頂點(diǎn)的入度和出度。 分別畫出有向圖的正鄰接鏈表和逆鄰接鏈表。 寫出相應(yīng)的鄰接矩陣表示。 寫出從頂點(diǎn)a開始的深度優(yōu)先和廣度優(yōu)先遍歷序列。 畫出從頂點(diǎn)a開始的深度優(yōu)先和廣度優(yōu)先生成樹。A：入度2出度2B：入度3出度1C:入度1出度2D:入度2出度1E入度1出度3 總計(jì)入度9 ;出度9a!-T3 I -Hi |a4|A|10 A(h) G的止鄰接鏈表(b) G的逆鄰接璉表a b c d ea01001從a點(diǎn)開

2、始深度優(yōu)先序列a-b-d-e-cbcde10 10000010 100001110 0廣度優(yōu)先遍歷序列：a-b-d-e-c(a)深度優(yōu)先生成樹(b)廣度優(yōu)先生成樹2. 對(duì)于圖7-27所示的帶權(quán)無向圖。 按照Prime算法給出從頂點(diǎn) 2開始構(gòu)造最小生成樹的過程。 按照Kruskal算法給出最小生成樹的過程。圖了-盤*?厝權(quán)尢向圖若從頂點(diǎn)2洌發(fā)構(gòu)造U=2t TE=； 先找權(quán)值晟小的邊(5 v,其中uWU且 vE V-U, 井且子罔不構(gòu)成砰*則U = UUv, TE=TEU(u, v *(3慎豆” fLfijU=V止.則TE中必有C 條邊.T=(U, T巳就能最小生成樹“CD(I)選取權(quán)值最小的邊(

3、v“ Vj), 若邊 Vj加入到TE后形成回路 則舍棄該邊(邊vjh否罠山 將該邊并入到TE中，即TE=TEU(Vj. Vj)-重復(fù)，直到TE中包含有rv圖7-27帶權(quán)無向時(shí)C3. 一個(gè)AOV網(wǎng)用鄰接矩陣表示，如圖7-31。用拓?fù)渑判蚯笤?AOV網(wǎng)的一個(gè)拓?fù)湫蛄?，給出相應(yīng)的步驟。(提示：先根據(jù)鄰接矩陣畫出有向圖，然后寫出可能的一個(gè)拓?fù)湫蛄?)Vo011Vi000v2000V.000000v5000V；000 0 0 011100 10 1()0000 0 0 10 0 0 I0 0 0 0圖7T1 個(gè)AOV網(wǎng)的鄰接矩陣相關(guān)知識(shí)：AOV網(wǎng)：圖中頂點(diǎn)表示活動(dòng)， 有向邊表示活動(dòng)之間的優(yōu)先關(guān)系，這樣的

4、有向圖稱為頂點(diǎn)表示活動(dòng)的網(wǎng)(Activity On Vertex Network ，AOV 網(wǎng))。?有向圖的拓?fù)渑判颍簶?gòu)造AOV網(wǎng)中頂點(diǎn)的一個(gè)拓?fù)渚€性序列(v；,v2, ? ,v,使得該線性序列不僅保持原來有向圖中頂點(diǎn)之間的優(yōu)先關(guān)系，而且對(duì)原圖中沒有優(yōu)先關(guān)系 的頂點(diǎn)之間也建立一種(人為的)優(yōu)先關(guān)系。算法思想： 在AOV網(wǎng)中選擇一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出； 在AOV網(wǎng)中刪除該頂點(diǎn)以及從該頂點(diǎn)出發(fā)的（以該頂點(diǎn)為尾的弧）所有有向?。ㄟ叄?； 重復(fù)、，直到圖中全部頂點(diǎn)都已輸出（圖中無環(huán)）或圖中不存在無前驅(qū)的頂點(diǎn)（圖中必有環(huán)）。V0-v1,v0-v2V1-v3,v1-v4,v1-v5V2-v4,v2-v6V

5、4-v6V5-v6入度為零，可畫圖V0-v1-v3-v5-v2-v4-v64. 假設(shè)一個(gè)工程的進(jìn)度計(jì)劃用 AOE網(wǎng)表示，如圖7-33所示。 求出每個(gè)事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間。 該工程完工至少需要多少時(shí)間？ 求出所有關(guān)鍵路徑和關(guān)鍵活動(dòng)。相關(guān)知識(shí):與AOV網(wǎng)相對(duì)應(yīng)的是 AOE(Activity On Edge)，是邊表示活動(dòng)的有向無環(huán)圖，圖中頂點(diǎn)表示 事件(Event),每個(gè)事件表示在其前的所有活動(dòng)已經(jīng)完成，其后的活動(dòng)可以開始；弧表示活 動(dòng)，弧上的權(quán)值表示相應(yīng)活動(dòng)所需的時(shí)間或費(fèi)用。頂點(diǎn)ViV4V5Nve(ij匚161821pi23252830W(i)6tsd6佃2226IT26183(Fa

6、1a3a5a6a?a9a10a 11313時(shí)園直i0566151821rii-23K2B10015619d23222226232S關(guān)犍路徑；V0-v2-v3-v6-v8-v9關(guān)鍵活動(dòng)型困4嗣聞2月145. 已知帶權(quán)有向圖如圖 7-29所示，請(qǐng)利用迪杰斯特拉 （Djkstra）算法從頂點(diǎn) V出發(fā)到其余 頂點(diǎn)的最短路徑及長度，給出相應(yīng)的求解步驟。圖7-29帶權(quán)有向圖 令S=Vs，用帶權(quán)的鄰接矩陣表示有向圖，對(duì)圖中每個(gè)頂點(diǎn) Vi按以下原則置初值: 選擇一個(gè)頂點(diǎn) Vj ,使得：distj=Min distk| V k V-S Vj就是求得的下一條最短路徑終點(diǎn)，將Vj并入到S中，即S=SU Vj o對(duì)V

7、-S中的每個(gè)頂點(diǎn) Vk，修改distk，方法是：若 distj+Wjkdistk，則修改為:distk=distj+Wjk( Vk V-S ) 重復(fù)，直到 S=V為止?；蛘卟捎靡韵路绞?終占八、i=1i=2i=3i=4i=5v1oo30(v4,v2,v1)30 (v4,v2,v1)v220(v4,v2)20(v4,v2)v3oooo45(v4,v2,v1,v3)45(v4,v2,v1,v3)v5oo50(v4,v2,v5)50(v4,v2,v5)50(v4,v2,v5)50(v4,v2,v5)v615(v4,v6)vjV6V2V1V3V5Sv4,v6v4,v6,v2v4,v6,v2,v1v4,v6,v2,v1,v3v4,v6,v2,v1,v3,v56.已知帶權(quán)有向圖如圖7-30所示，請(qǐng)利用弗洛伊德（Floyd）算法求出每對(duì)頂點(diǎn)之間的最短路徑及路徑長度。07-30帶權(quán)有向圖abcd|efaoo535acd8ace9abfb13bfeao16beac