拓?fù)渑判蚝完P(guān)鍵路徑(參考版)
2025-05-13 00:41本頁面
【正文】 1 2 4 6 10 3 7 9 8 5 8 3 4 14 10 19 8 6 13 9 9 10 6 7 2 。 實(shí)際應(yīng)用中采用那一種圖，取決于要求解的問題。 若 ai由弧 vk， vj表示，則 ai的最晚開始時(shí)間要保證事件 vj的最遲發(fā)生時(shí)間不拖后。 ⑵ 事件的最遲發(fā)生時(shí)間 vl[k] vj vj vk vl[k]=min{vl[j]lenvk , vj}（ vk, vj∈ s[k]） s[k]為所有從 vk發(fā)出的有向邊的集合 AOE網(wǎng)應(yīng)用：關(guān)鍵路徑 40 v2 v7 v6 v5 v4 v1 v3 v9 v8 ve[k] vl[k] 0 6 4 5 7 7 16 14 18 18 14 16 10 7 8 6 6 0 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 vl[k]=min{vl[j]lenvk , vj} AOE網(wǎng)應(yīng)用：關(guān)鍵路徑 41 ⑶ 活動(dòng)的最早開始時(shí)間 e[i] 若活動(dòng) ai是由弧 vk , vj表示，則活動(dòng) ai的最早開始時(shí)間應(yīng)等于事件 vk的最早發(fā)生時(shí)間。這個(gè)長度決定了所有從頂點(diǎn) vk發(fā)出的活動(dòng)能夠開工的最早時(shí)間。 活動(dòng) ak的最晚開始時(shí)間 l[k]， 它的弧頭頂點(diǎn)事件允許的最晚發(fā)生時(shí)間減去該活動(dòng)持續(xù)的時(shí)間。 事件 Vj 的最遲發(fā)生時(shí)間 Vl[j]， 指在不推遲整個(gè)工期的前提下，事件最晚必須發(fā)生的時(shí)間。這條路徑長度最長的路徑就叫做 關(guān)鍵路徑 。 33 a b c d e f g h k 6 4 5 2 1 1 8 7 2 4 4 例如 : 整個(gè)工程完成的時(shí)間為 ：從有向圖的 始點(diǎn) 到 終點(diǎn) 的最長路徑 始點(diǎn) 終點(diǎn) 34 V3 V1 V4 V6 V5 V2 a4=3 a1=3 a2=2 a6=3 a5=4 a3=2 a7=2 a8=1 頂點(diǎn)表示事件 邊表示活動(dòng) 事件 Vj發(fā)生表示 ak已結(jié)束 ak Vj Vi 事件 Vi發(fā)生表示 ak可以開始 AOE網(wǎng) 一、有向無環(huán)圖及其應(yīng)用 35 一、有向無環(huán)圖及其應(yīng)用 AOE網(wǎng)可以回答下列問題： 1. 完成整個(gè)工程 至少 需要多少時(shí)間 ? 2. 為縮短完成工程所需的時(shí)間 , 應(yīng)當(dāng)加快哪些活動(dòng) ? 從始點(diǎn)到終點(diǎn)的路徑可能不止一條，只有各條路徑上所有活動(dòng)都完成了，整個(gè)工程才算完成。AOE網(wǎng)中沒有入邊的頂點(diǎn)稱為 始點(diǎn) （或源點(diǎn)），沒有出邊的頂點(diǎn)稱為 終點(diǎn) （或匯點(diǎn)）。 // g有回路 else return SUCCESS。 } } delete []indegree。 v2 = (v1, v2)) { // v2為 v1的一個(gè)鄰接點(diǎn) if (indegree[v2] == 0)//鄰接點(diǎn)入度減 1 (v2)。 // 對輸出頂點(diǎn)進(jìn)行記數(shù) for (int v2 = (v1)。 // 取出一個(gè)入度為 0的頂點(diǎn) cout v1 。// 建立入度為 0的頂點(diǎn)隊(duì)列 } 31 while (!()) { // 隊(duì)列非空 int v1。 v ()。 StatIndegree(g, indegree)。 //入度數(shù)組 LinkQueueint q。 30 template class ElemType StatusCode TopSort(const AdjMatrixDirGraphElemType amp。 頂點(diǎn)表結(jié)點(diǎn) in vertex firstedge 2. 棧 S：存儲(chǔ)所有無前驅(qū)的頂點(diǎn) 。 因?yàn)閳D中存在一個(gè)回路 {B, C, D} 12 一、有向無環(huán)圖及其應(yīng)用 拓?fù)渑判蚍椒ǎ? 第一步： 在有向圖選一無前趨的頂點(diǎn) v，輸出； 第二步： 從有向圖中刪除 v及以 v為尾的孤； 重復(fù) 第一步和第二步 ，直到輸出全部頂點(diǎn)或有向圖中不存在無前趨頂點(diǎn)（此時(shí)圖中存在環(huán)）。 例 7 c1 c2 c3 c4 c5 c6 c7 C8
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號(hào)-1