數(shù)據(jù)結構羅吳蔓電子科大ppt考研chapt739-wenkub.com
2025-12-20 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 終點 從 v0 到各終點的 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) 最短路徑 二、每一對頂點之間的最短路徑 兩種方法：每次以一個頂點為源點，重復調(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 的中間頂點的序號不大于 k 的最短路徑長度。 又如 a6推遲 3天開始，或拖延 3天完成 （ a6=6）均不影響整個工期 ? 分析關鍵路徑的目的是找出影響整個工期的關鍵活動，縮短關鍵活動的持續(xù)時間，?？梢钥s短整個工期。 為此，采用鄰接表作為 AOV網(wǎng)的存儲結構，并在頭結點中增加一個存放頂點入度的域（ indegree） 關鍵路徑 一、 AOE網(wǎng)（ activity on edge） 若有向圖中，頂點表示事件，弧表示活動，弧上的權表示完成該活動所需的時間，則稱這類有向圖為邊表示活動的網(wǎng)（ AOE網(wǎng)） AOE網(wǎng)中僅有一個入度為 0的事件，稱為 源點 ，它表示工程的開始；網(wǎng)中也僅有一個出度為 0的事件，稱為 匯點 ，它表示工程的結束。顯然，有回路，整個工程就無法結束 （ 2）確定各項活動在整個工程執(zhí)行中的先后順序。 ? 若（ v, u） 依附的頂點 v和 u落在 T中不同的連通分量上， 則將邊（ v, u）并入到 T的邊集中； 否則，舍去該邊，選擇下一條代價最小的邊 . 四、克魯斯卡爾（ 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 代價 =15 拓撲排序 (topological sort) 拓撲排序是一種對非線性結構的有向圖進行線性化的重要手段 一、 AOV網(wǎng) (Activity on vertex work) 一個有向圖可用來表示一個施工流程圖、一個產(chǎn)品生產(chǎn)流程圖、或一個程序框圖等。 U VU u’ v u’ v’ 含義：將頂點分為兩個不相交的集合 U和 VU， 若邊（ u， v）是連接這兩個頂點集的最小權 值邊，則邊（ u， v）必然是某最小生成樹的邊。 最小生成樹也不一定唯一。 visited[w]:=true。 ENQUEUE(Q,vo)。 {NEXTADJ} 思考： traver調(diào)用 dfs的次數(shù)由什么決定？ 圖的遍歷 二、廣度優(yōu)先搜索（ breadthfirstsearch) (1)首先訪問指定 頂點 v0，將 v0作為當前頂點 (2)訪問當前頂點的 所有未訪問過的鄰接點 ，并 依次將訪問的這些鄰接點作為當前頂點 (3)重復 (2)， 直到 所有頂點 被訪問為止 對圖 4廣度優(yōu)先搜索，訪問頂點序列為： 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 的第一個鄰接點 } WHILE w0 do [ IF NOT visited[w] THEN dfs(g,w)。V0:vtxptr)。 ARRAY[vtxptr] OF boolean)。只是在 第 i條鏈表 上的結點是以 Vi為 弧頭 的各個 弧尾 頂點 1 2 3 4 1 1 4 3 1 2 3 4 此時，第 i條鏈表上的結點數(shù)，為 Vi的入度 如圖 G1的逆鄰接表為： 圖的遍歷 從圖中某個頂點出發(fā)，沿路徑使圖中 每個頂點 被 訪問且僅被訪問一次 的過程，稱為 遍歷圖 。 圖的存儲結構
教學課件相關推薦
鄂ICP備17016276號-1