拓?fù)渑判蚝完P(guān)鍵路徑-文庫吧在線文庫
【正文】 ： C1C2C3C4C5C7C9 C10C11C6 （ 10） C8 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C10C11C6C12 （ 11） 拓?fù)湫蛄校?C1C2C3C4C5C7C9 C10C11C6C12C8 （ 12） 18 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 拓?fù)湫蛄校?C1C2C3C4C5C7C9C10C11C6C12C8 或 ： C9C10C11C6C1C12C4C2C3C5C7C8 一個 AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏? 如何在計算機(jī)上實(shí)現(xiàn) 對有向圖的拓?fù)渑判颍? 19 a b c g h d f e a b h c d g f e 20 一、有向無環(huán)圖及其應(yīng)用 （ 1） 選擇一入度為 0 頂點(diǎn) v，輸出； （ 2） 將 v 鄰接到的頂點(diǎn)的入度減 1； （ 3） 重復(fù) 12，直到輸出全部頂點(diǎn)或圖中沒有入度為 0的頂點(diǎn)； 拓?fù)渑判蛏婕暗臄?shù)據(jù)和操作： 數(shù)據(jù)： 有向圖，頂點(diǎn)的入度； 操作： （ 1） 選擇一入度為 0 頂點(diǎn) v，輸出； （ 2） 將 v 鄰接到的頂點(diǎn) u 的入度減 1； 拓?fù)渑判蛩惴? 21 設(shè)計數(shù)據(jù)結(jié)構(gòu) 1. 圖的存儲結(jié)構(gòu)：采用鄰接表存儲 ，在頂點(diǎn)表中增加一個入度域。 // 統(tǒng)計頂點(diǎn)的入度 for (int v = 0。 v2 != 1。 AOE網(wǎng)的性質(zhì)： ⑴ 只有在某頂點(diǎn)所代表的事件發(fā)生后 ， 從該頂點(diǎn)出發(fā)的各活動才能開始； ⑵ 只有在進(jìn)入某頂點(diǎn)的各活動都結(jié)束 ， 該頂點(diǎn)所代表的事件才能發(fā)生 。 活動 ak 的時間余量 diff[k] =l[k]e[k]時間余量為 0者即為關(guān)鍵活動 ak Vj Vi 37 ve[k]是指從始點(diǎn)開始到頂點(diǎn) vk的最大路徑長度。 一、有向無環(huán)圖及其應(yīng)用 ? 關(guān)鍵路徑 48 本 講 小 結(jié) 重點(diǎn)： 拓?fù)渑判? 難點(diǎn)： 關(guān)鍵路徑 49 Homework: ?給出下面 AOE網(wǎng)中，各活動的最早開始時間和最遲開始時間，以及該 AOE網(wǎng)的關(guān)鍵路徑。因此，有： e[i]=ve[k] AOE網(wǎng)應(yīng)用：關(guān)鍵路徑 42 v2 v1 v3 v4 v5 v8 v6 v7 v9 a1=6 a4=1 a7=9 a10=2 a11=4 a8=7 a9=4 a5=1 a6=2 a3=5 a2=4 v2 v7 v6 v5 v4 v1 v3 v9 v8 ve[k] 0 6 4 5 7 7 16 14 18 a2 a7 a6 a5 a4 a1 a3 a9 a8 e[i] 0 0 0 6 4 5 7 7 7 a10 a11 16 14 e[i]=ve[k] AOE網(wǎng)應(yīng)用：關(guān)鍵路徑 43 活動 ai的最晚開始時間是指，在不推遲整個工期的前提下， ai必須開始的最晚時間。 36 一、有向無環(huán)圖及其應(yīng)用 事件 Vj 的最早發(fā)生時間 Ve[j]， 是從源點(diǎn)到頂點(diǎn) Vj的最大路徑長度。 // 釋放 indegree所占用的存儲空間 if (count ()) return FAIL。 (v1)。g) // 初始條件：存在有向圖 g // 操作結(jié)果：如 g無回路 ,則輸出 g的頂點(diǎn)的一個拓?fù)湫蛄?, // 并返回 SUCCESS,否則返回 FAIL { int *indegree = new int[()]。這樣在有的課程之間有 領(lǐng)先關(guān)系，有的課程可以 并行 地學(xué)習(xí)。1 Essential of Lecture Sixteen ： 一、拓?fù)渑判? 二 、 關(guān)鍵路徑 2 一、有向無環(huán)圖及其應(yīng)用 ?有向無環(huán)圖：沒有回路的有向圖 （ a） 有向樹 （ b） 有向無環(huán)圖 （ c） 有向圖 問題： 判斷一個有向圖是否為有向無環(huán)圖的方法是？ 3 一、有向無環(huán)圖及其應(yīng)用 應(yīng)用： 工程流程、生產(chǎn)過程中各道工序的流
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1