數(shù)據(jù)結(jié)構(gòu)羅吳蔓電子科大ppt考研chapt739-wenkub.com
2024-12-30 16:07 本頁面
【正文】 最短路徑 ? 例子 ① ② ③④⑤0 5 10 50 30 100 60 10 20 cost 0 1 2 3 4 5 ∞∞∞∞∞∞∞∞∞∞∞∞∞∞ ∞∞ 10 5 ∞∞∞∞∞∞∞ 50 20 30 ∞∞∞∞100 10 60 ∞0 1 2 3 4 5 終點(diǎn) 從 v0 到各終點(diǎn)的 dist 值和最短路徑 v1 v2 v4 v3 v5 vj 60(v0,v4,v3,v5) v5 ∞50(v0,v4,v3) 90(v0,v4,v5) v3 ∞ ∞10(v0,v2) 30(v0,v4) 100(v0,v5) v2 ∞∞ 60(v0,v2,v3) v4 ∞30(v0,v4) 100(v0,v5) 最短路徑 二、每一對(duì)頂點(diǎn)之間的最短路徑 兩種方法：每次以一個(gè)頂點(diǎn)為源點(diǎn)，重復(fù)調(diào)用 Dijkstra算法 n次； 弗洛伊德算法 (Floyd) ：以 A(0) [i,j]=cost[i,j] 遞推出：A(k)[i,j]=Min{A(k1)[i,j], A(k1)[i,k]+ A(k1) [k,j]},1≤k≤n 其中， A[k][i,j] 表示從 vi到 vj 的中間頂點(diǎn)的序號(hào)不大于 k 的最短路徑長(zhǎng)度。 又如 a6推遲 3天開始，或拖延 3天完成 （ a6=6）均不影響整個(gè)工期 ? 分析關(guān)鍵路徑的目的是找出影響整個(gè)工期的關(guān)鍵活動(dòng)，縮短關(guān)鍵活動(dòng)的持續(xù)時(shí)間，?？梢钥s短整個(gè)工期。 為此，采用鄰接表作為 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é)束。顯然，有回路，整個(gè)工程就無法結(jié)束 （ 2）確定各項(xiàng)活動(dòng)在整個(gè)工程執(zhí)行中的先后順序。 ? 若（ v, u） 依附的頂點(diǎn) v和 u落在 T中不同的連通分量上， 則將邊（ v, u）并入到 T的邊集中； 否則，舍去該邊，選擇下一條代價(jià)最小的邊 . 四、克魯斯卡爾（ Kruskal） 最小生成樹算法 ② ① ④ ⑤ 5 2 1 ③ 3 4 6 6 5 5 6 ⑥ 步驟 (v, u) E T ② ① ④ ⑤ 5 2 ③ 3 4 6 6 5 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ ② ① ④ ⑤ ③ ⑥ 1 (1, 3) 0 四、克魯斯卡爾（ Kruskal） 最小生成樹算法 ② ① ④ ⑤ 5 ③ 3 4 6 6 5 5 6 ⑥ 步驟 (v, u) E 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è)程序框圖等。 U VU u’ v u’ v’ 含義：將頂點(diǎn)分為兩個(gè)不相交的集合 U和 VU， 若邊（ u， v）是連接這兩個(gè)頂點(diǎn)集的最小權(quán) 值邊，則邊（ u， v）必然是某最小生成樹的邊。 最小生成樹也不一定唯一。 visited[w]:=true。 ENQUEUE(Q,vo)。 {NEXTADJ} 思考： traver調(diào)用 dfs的次數(shù)由什么決定？ 圖的遍歷 二、廣度優(yōu)先搜索（ breadthfirstsearch) (1)首先訪問指定 頂點(diǎn) v0，將 v0作為當(dāng)前頂點(diǎn) (2)訪問當(dāng)前頂點(diǎn)的 所有未訪問過的鄰接點(diǎn) ，并 依次將訪問的這些鄰接點(diǎn)作為當(dāng)前頂點(diǎn) (3)重復(fù) (2)， 直到 所有頂點(diǎn) 被訪問為止 對(duì)圖 4廣度優(yōu)先搜索，訪問頂點(diǎn)序列為： V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 V5 V6 V7 V8 圖的遍歷 二、廣度優(yōu)先搜索（ breadthfirstsearch) 廣度優(yōu)先搜索算法： PROC bfs(g,vo)。{FIRSTADJ} FUNC NEXTADJ(g,vo,w)。 {找 V0 的第一個(gè)鄰接點(diǎn) } WHILE w0 do [ IF NOT visited[w] THEN dfs(g,w)。V0:vtxptr)。 ARRAY[vtxptr] OF boolean)。只是在 第 i條鏈表 上的結(jié)點(diǎn)是以 Vi為 弧頭 的各個(gè) 弧尾 頂點(diǎn) 1 2 3 4 1 1 4 3 1 2 3 4 此時(shí)，第 i條鏈表上的結(jié)點(diǎn)數(shù)，為 Vi的入度 如圖 G1的逆鄰接表為： 圖的遍歷 從圖中某個(gè)頂點(diǎn)出發(fā)，沿路徑使圖中 每個(gè)頂點(diǎn) 被 訪問且僅被訪問一次 的過程，稱為 遍歷圖 。 圖的存儲(chǔ)結(jié)構(gòu)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1