數(shù)據(jù)結(jié)構(gòu)羅吳蔓電子科大ppt考研chapt739(已改無錯(cuò)字)
2023-01-20 16:07:15 本頁(yè)面
【正文】 T 3 (2, 5) 2 (4, 6) ② ① ④ ⑤ ③ ⑥ ② ① ④ ⑤ 5 ③ 4 6 6 5 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ 四、克魯斯卡爾（ Kruskal） 最小生成樹算法 步驟 (v, u) E T 5 (1, 4) 4 (3, 6) ② ① ④ ⑤ 5 ③ 6 6 5 5 6 ⑥ ② ① ④ ⑤ ③ 6 6 5 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ ② ① ④ ⑤ ③ ⑥ 四、克魯斯卡爾（ Kruskal） 最小生成樹算法 步驟 (v, u) E T 6 (2, 3) ② ① ④ ⑤ ③ 6 6 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ 邊數(shù) =n1=5 代價(jià) =15 拓?fù)渑判?(topological sort) 拓?fù)渑判蚴且环N對(duì)非線性結(jié)構(gòu)的有向圖進(jìn)行線性化的重要手段 一、 AOV網(wǎng) (Activity on vertex work) 一個(gè)有向圖可用來表示一個(gè)施工流程圖、一個(gè)產(chǎn)品生產(chǎn)流程圖、或一個(gè)程序框圖等。如圖： a1 a5 a4 a6 a2 a3 a8 a7 a9 課程安排 Pascal DS Compiler OS C 施工從活動(dòng) a a2開始，到達(dá)活動(dòng) a8和 a9時(shí)，整個(gè)施工結(jié)束。這類 有向圖中，頂點(diǎn)表示活動(dòng)，弧 ai， aj 表示活動(dòng) ai優(yōu)先于活動(dòng) aj ， 稱這類有向圖為頂點(diǎn)表示活動(dòng)的網(wǎng)（ AOV網(wǎng)）。 拓?fù)渑判?(topological sort) AOV網(wǎng)可解決如下兩個(gè)問題： （ 1）判定工程的可行性。顯然，有回路，整個(gè)工程就無法結(jié)束 （ 2）確定各項(xiàng)活動(dòng)在整個(gè)工程執(zhí)行中的先后順序。 稱這種先后順序?yàn)?拓?fù)溆行蛐蛄?。 如圖有如下拓?fù)溆行蛐蛄校? a1 a2 a3a4 a5 a6 a7 a8 a9 a2 a6 a1 a3 a4 a5 a7 a9 a8 a1 a5 a4 a6 a2 a3 a8 a7 a9 二、拓?fù)渑判蛩惴? 算法步驟 (1) 在 AOV網(wǎng)中，選取一個(gè)沒有前驅(qū)的頂點(diǎn)輸出； (2) 刪除該頂點(diǎn)和所有以它為弧尾的弧； (3) 重復(fù)以上兩步，直到 ? AOV網(wǎng)中全部頂點(diǎn)都已輸出（得到拓?fù)溆行蛐蛄校? ? 或者，圖中再無沒有前驅(qū)的頂點(diǎn)（ AOV網(wǎng)中有環(huán)） 二、拓?fù)渑判蛩惴? 如何實(shí)現(xiàn)算法中的 (1)和 (2)？ ? 對(duì)于 (1)，沒有前驅(qū)的頂點(diǎn)即入度為 0的頂點(diǎn)； ? 對(duì)于 (2)，刪除以它為弧尾的所有弧，即讓該頂點(diǎn)的所有直接后繼的入度減 1。 由此分析知：拓?fù)渑判蛩惴ǖ膶?shí)現(xiàn)與頂點(diǎn)的入度有密切關(guān)系，因此，在選取存儲(chǔ)結(jié)構(gòu)時(shí)，應(yīng)考慮： ? 能容易得到各頂點(diǎn)的入度； ? 有利于尋找任一頂點(diǎn)的所有直接后繼。 為此，采用鄰接表作為 AOV網(wǎng)的存儲(chǔ)結(jié)構(gòu)，并在頭結(jié)點(diǎn)中增加一個(gè)存放頂點(diǎn)入度的域（ indegree） 關(guān)鍵路徑 一、 AOE網(wǎng)（ activity on edge） 若有向圖中，頂點(diǎn)表示事件，弧表示活動(dòng)，弧上的權(quán)表示完成該活動(dòng)所需的時(shí)間，則稱這類有向圖為邊表示活動(dòng)的網(wǎng)（ AOE網(wǎng)） AOE網(wǎng)中僅有一個(gè)入度為 0的事件，稱為 源點(diǎn) ，它表示工程的開始；網(wǎng)中也僅有一個(gè)出度為 0的事件，稱為 匯點(diǎn) ，它表示工程的結(jié)束。 每一事件 V表示以它為弧頭的所有活動(dòng)已經(jīng)完成，同時(shí)，也表示以它為弧尾的所有活動(dòng)可以開始。 關(guān)鍵路徑 AOE網(wǎng)可解決如下問題： ? 估算工程的最短工期（從源點(diǎn)到 匯點(diǎn)至少需要多少時(shí)間） ? 找出哪些活動(dòng)是影響整個(gè)工程進(jìn)展的關(guān)鍵 ① ② ③ ⑤ a1=6 a4=1 a2=4 a5=1 有 4個(gè)事件： V1， V2， V3， V5 V1為源點(diǎn)， V5為匯點(diǎn) 有 4個(gè)活動(dòng)： a1, a2, a4, a5 V3表示： a2已完成， a5可以開始 關(guān)鍵路徑 二、幾個(gè)術(shù)語(yǔ) ? 路徑長(zhǎng)度 ： 路徑上各活動(dòng)持續(xù)時(shí)間的總和 （ 即：路徑上所有弧的權(quán)值之和 ） ? 關(guān)鍵路徑 ： 從源點(diǎn)到匯點(diǎn)之間路徑長(zhǎng)度最長(zhǎng)的路徑 （ 不一定唯一 ） ? 事件 V i的最早發(fā)生時(shí)間 ve(i)： 從源點(diǎn)到 V i的最長(zhǎng)路徑長(zhǎng)度 ? 活動(dòng) ai的最早開始時(shí)間 e(i)： 等于該活動(dòng)的弧尾事件 V j的最早發(fā)生時(shí)間 即若 j, k表示活動(dòng) ai ，則有 e(i)=ve(j) vj vk ai 關(guān)鍵路徑 ? 事件 vk 的最遲發(fā)生時(shí)間 vl(k)： 是在不推遲整個(gè)工期的前提下，該事件最遲必須發(fā)生的時(shí)間 ? 活動(dòng) ai的最遲開始時(shí)間 L(i)： 是該活動(dòng)的弧頭事件的最遲發(fā)生時(shí)間與該活動(dòng)的持續(xù)時(shí)間之差， 即 L(i)=vl(k) ai 的持續(xù)時(shí)間 ? 關(guān)鍵活動(dòng)： l(i)=e(i)的活動(dòng) 由此可見：在 AOE網(wǎng)中找關(guān)鍵活動(dòng)問題可轉(zhuǎn)化為求 l(i)=e(i)， 而 e(i)=ve(j) l(i)=vl(k) ai 的持續(xù)時(shí)間 因此，需先求出事件 的最早、最遲發(fā)生時(shí)間 關(guān)鍵路徑 三、關(guān)鍵路徑算法思想 1. 從 ve(1)=0 開始利用下面遞推公式，計(jì)算出各事件的最早發(fā)生時(shí)間 ve(j)=Max{ve(i)+dut(i, j)}， j=2, …… , n ， i, j ∈T 其中： T是所有以 j為頭的弧集合， dut(i,j)表示活動(dòng)的持續(xù)時(shí)間 前例中， ve(5)=Max{ve(2)+dut(2,5)， ve(3)+dut(3,5)} =Max{6+1,4+1}=7 ① ② ③ ⑤ a1=6 a4=1 a2=4 a5=1 2. 從 vl(n)=ve(n)開始，利用下面遞推公式，計(jì)算出各事件的最遲發(fā)生時(shí)間： vl(i)=Min{vl(j)dut(i, j)} i=n1 , …… , 2 , 1 , i, j ∈S 其中： S是所有以 i為尾的弧集合 關(guān)鍵路徑 關(guān)鍵路徑 3. 設(shè)活動(dòng) ai由弧 j, k表示，其持續(xù)時(shí)間為dut(j,k)，則利用下面公式，計(jì)算出各活動(dòng)的最早、最遲開始時(shí)間： e(i)=ve(j)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1