拓撲排序和關鍵路徑-wenkub
2023-05-20 00:41:08 本頁面
【正文】 12 拓撲序列： C1C2C3C4C5C7C9C10C11C6C12C8 或 ： C9C10C11C6C1C12C4C2C3C5C7C8 一個 AOV網(wǎng)的拓撲序列不是唯一的 如何在計算機上實現(xiàn) 對有向圖的拓撲排序？ 19 a b c g h d f e a b h c d g f e 20 一、有向無環(huán)圖及其應用 （ 1） 選擇一入度為 0 頂點 v，輸出； （ 2） 將 v 鄰接到的頂點的入度減 1； （ 3） 重復 12，直到輸出全部頂點或圖中沒有入度為 0的頂點； 拓撲排序涉及的數(shù)據(jù)和操作： 數(shù)據(jù)： 有向圖，頂點的入度； 操作： （ 1） 選擇一入度為 0 頂點 v，輸出； （ 2） 將 v 鄰接到的頂點 u 的入度減 1； 拓撲排序算法 21 設計數(shù)據(jù)結構 1. 圖的存儲結構：采用鄰接表存儲 ，在頂點表中增加一個入度域。這樣在有的課程之間有 領先關系，有的課程可以 并行 地學習。 為求解工程流程是否 “ 合理 ” ，通常用 AOV網(wǎng) 的有向圖表示工程流程。1 Essential of Lecture Sixteen ： 一、拓撲排序 二 、 關鍵路徑 2 一、有向無環(huán)圖及其應用 ?有向無環(huán)圖：沒有回路的有向圖 （ a） 有向樹 （ b） 有向無環(huán)圖 （ c） 有向圖 問題： 判斷一個有向圖是否為有向無環(huán)圖的方法是？ 3 一、有向無環(huán)圖及其應用 應用： 工程流程、生產(chǎn)過程中各道工序的流程、程序流程、課程的流程。 ? 拓撲排序 5 某工程可分為 6個子工程，若用 頂點表示子工程（也稱活動） , 用弧表示子工程間的順序關系。 例 7 c1 c2 c3 c4 c5 c6 c7 C8 c9 c10 c11 c12 程序設計 離散數(shù)學 數(shù)據(jù)結構 匯編語言 算法分析 計算機體系 編譯方法 操作系統(tǒng) 高等數(shù)學 線性代數(shù) 電子電路 數(shù)值分析 無 c1 c1,c2 c1 c3,c4 c11 c5,c3 c3,c6 無 c9 c9 c9,c10,c1 課程編號 課程名稱 先決條件 c4 c1 c2 c3 c12 c9 c10 c11 c6 c7 c8 c5 ?例 2: 課程流程圖 如何安排施工計劃？ 如何安排教學計劃？ 8 一個可行的施工計劃為： A,B,C, D,E,F 一個可行的學習計劃為：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8 可行的計劃的特點： 若在流程圖中頂點 v是頂點 u 的前趨，則在計劃序列中頂點 v 也是 u的前趨。 頂點表結點 in vertex firstedge 2. 棧 S：存儲所有無前驅的頂點 。 //入度數(shù)組 LinkQueueint q。 v ()。 // 取出一個入度為 0的頂點 cout v1 。 v2 = (v1, v2)) { // v2為 v1的一個鄰接點 if (indegree[v2] == 0)//鄰接點入度減 1 (v2)。 // g有回路 else return SUCCESS。 33 a b c d e f g h k 6 4 5 2 1 1 8 7 2 4 4 例如 : 整個工程完成的時間為 ：從有向圖的 始點 到 終點 的最長路徑 始點 終點 34 V3 V1 V4 V6 V5 V2 a4=3 a1=3 a2=2 a6=3 a5=4 a3=2 a7=2 a8=1 頂點表示事件 邊表示活動 事件 Vj發(fā)生表示 ak已結束 ak Vj Vi 事件 Vi發(fā)生表示 ak可以開始 AOE網(wǎng) 一、有向無環(huán)圖及其應用 35 一、有向無環(huán)圖及其應用 AOE網(wǎng)可以回答下列問題： 1. 完成整個工程 至少
環(huán)評公示相關推薦
鄂ICP備17016276號-1