數(shù)據(jù)結(jié)構(gòu)羅吳蔓電子科大ppt考研chapt739(編輯修改稿)
2025-01-19 16:07 本頁面
【文章內(nèi)容簡介】 ETURN(0) ELSE RETURN (p↑.adjvex) ENDF。{FIRSTADJ} FUNC NEXTADJ(g,vo,w)。 p:=adjlist[vo].firstarc。 WHILE pNIL AND p↑.adjvexw DO p:= p↑.nextarc。 IF p=NIL COR p↑.nextarc=NIL THEN RETURN(0) ELSE RETURN(p↑.nextarc↑.adjvex) ENDP。 {NEXTADJ} 思考： traver調(diào)用 dfs的次數(shù)由什么決定？ 圖的遍歷 二、廣度優(yōu)先搜索（ breadthfirstsearch) (1)首先訪問指定 頂點 v0，將 v0作為當(dāng)前頂點 (2)訪問當(dāng)前頂點的 所有未訪問過的鄰接點 ，并 依次將訪問的這些鄰接點作為當(dāng)前頂點 (3)重復(fù) (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)。 visited(vo)。 visited[vo]:=true。 INIQUEUE(Q)。 ENQUEUE(Q,vo)。 WHILE NOT EMPTY(Q) DO [ v:=DLQUEUE(Q)。 w:=FIRSTADJ(g,v)。 WHILE w0 DO [ IF NOT visited[w] THEN [ visite(w)。 visited[w]:=true。 ENQUEWE(Q,w) ]。 w:=NEXTADJ(g,v,w) ] ] ENDP。 {bfs} 最小生成樹 一、最小生成樹概念 1. 設(shè)無向連通圖 G=（ V， {E}）， 其子圖 G’ =（ V， {T}） 滿足： ① V(G’ )=V(G) n個頂點 ② G’是連通的 ③ G’中無回路 則 G’是 G的生成樹 最小生成樹 具有 n個頂點的無向連通圖 G ? 其任一生成樹 G’恰好含 n1條邊 ? 生成樹不一定唯一，如 4個頂點選擇 3條邊有 如下 5種形狀 (5 4= 20種 ): 其中 16種為生成樹 ,（保證了連通） 生成樹代價 對圖中每條邊賦于一個權(quán)值（代價），則構(gòu)成一個網(wǎng)， 網(wǎng)的生成樹 G’ =(V,{T})的 代價 是 T中各邊的權(quán)值之和， 最小生成樹就是網(wǎng)上所有可能的生成樹中， 代價最小的一類生成樹。 最小生成樹也不一定唯一。 最小生成樹 最小生成樹的實用例子很多 例 1： N臺計算機之間建立通訊網(wǎng) 頂點表示 puter 邊表示通訊線 權(quán)值表示通訊線的代價（通訊 線長度， puter間距離等） 要求： ① n臺計算機中的任何兩臺能通過網(wǎng)進行通訊； ② 使總的代價最小。 求最小生成樹 [T] 最小生成樹 最小生成樹的實用例子 例 2： 郵遞員送信線路 [T] 頂點表示投遞點 邊表示街道 權(quán)值表示街道的長度 要求： ① 完成 n個投遞點的投遞； ② 使總路徑長度最短 , 即求最小生成樹 [T] 最小生成樹 二、最小生成樹性質(zhì) MST 設(shè) N=（ V， {E}）是一個連通網(wǎng)， U是頂點集 V的一個非空子集。 若（ u， v）是一條具有最小權(quán)值的邊，其中 u∈U,v∈V U, 即（ u， v） =Min{cost(x,y)|x∈U,y∈V U} 則必存在一棵包含邊（ u， v）的最小生成樹。 U VU u’ v u’ v’ 含義：將頂點分為兩個不相交的集合 U和 VU， 若邊（ u， v）是連接這兩個頂點集的最小權(quán) 值邊，則邊（ u， v）必然是某最小生成樹的邊。 三、普里姆（ Prim）最小生成樹算法 設(shè) N=（ V， {E}）是一個連通網(wǎng)， V={1， 2， … ， n}是 N的頂點集合， 輔助集合 U，初值為 {Uo}， 用來存放當(dāng)前所得到的最小生成樹的頂點； 輔助集合 TE，初值為 {}， 用來存放當(dāng)前所得到的最小生成樹的邊。 Prim算法步驟 1. TE=Ф,U={u0} 2. 當(dāng) U≠V ，重復(fù)下列步驟： (1)選?。?u0,v0)=min{cost(u,v)|u∈U,v∈V U}，保證不形成回路 (2)TE=TE+（ u0,v0), 邊（ u0,v0)并入 TE (3)U=U+{v0}， 頂點 V0 并入 U 初始化： ① ② ① ④ ⑤ 5 2 1 ③ 3 4 6 6 5 5 6 ⑥ ① 1 ③ 第 1步： 6 ① 1 ③ 4 第 2步： ④ 6 ① 1 ③ 4 2 第 3步： 5 ② ④ 6 ① 1 ③ 4 2 第 4步： 2 3 ⑤ ② 5 ④ 6 ① 1 ③ 4 第 5步： 特點 : 以連通為主 選代價最小的鄰接邊 四、克魯斯卡爾（ Kruskal） 最小生成樹算法 Kruskal 算法是逐步給生成樹 T中添加不和 T中的邊構(gòu)成回路的當(dāng)前最小代價邊。 特點 : 以最小代價邊為主 設(shè) N=（ V， {E}）是個連通網(wǎng) , 算法步驟為： 1. 置生成樹 T的初始狀態(tài)為 T=（ V， {Ф}） 2. 當(dāng) T中邊數(shù) n1時 , 重復(fù)下列步驟 : ? 從 E中選取代價最小的邊（ v, u） , 并刪除之 。 ? 若（ 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
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1