數據結構羅吳蔓電子科大ppt考研chapt739(編輯修改稿)

　

【文章內容簡介】 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調用 dfs的次數由什么決定？ 圖的遍歷 二、廣度優先搜索（ breadthfirstsearch) (1)首先訪問指定 頂點 v0，將 v0作為當前頂點 (2)訪問當前頂點的 所有未訪問過的鄰接點 ，并 依次將訪問的這些鄰接點作為當前頂點 (3)重復 (2)， 直到 所有頂點 被訪問為止 對圖 4廣度優先搜索，訪問頂點序列為： V1 V2 V3 V4 V5 V6 V7 V8 V1 V2 V3 V4 V5 V6 V7 V8 圖的遍歷 二、廣度優先搜索（ breadthfirstsearch) 廣度優先搜索算法： 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. 設無向連通圖 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種為生成樹 ,（保證了連通） 生成樹代價 對圖中每條邊賦于一個權值（代價），則構成一個網， 網的生成樹 G’ =(V,{T})的 代價 是 T中各邊的權值之和， 最小生成樹就是網上所有可能的生成樹中， 代價最小的一類生成樹。 最小生成樹也不一定唯一。 最小生成樹 最小生成樹的實用例子很多 例 1： N臺計算機之間建立通訊網 頂點表示 puter 邊表示通訊線 權值表示通訊線的代價（通訊 線長度， puter間距離等） 要求： ① n臺計算機中的任何兩臺能通過網進行通訊； ② 使總的代價最小。 求最小生成樹 [T] 最小生成樹 最小生成樹的實用例子 例 2： 郵遞員送信線路 [T] 頂點表示投遞點 邊表示街道 權值表示街道的長度 要求： ① 完成 n個投遞點的投遞； ② 使總路徑長度最短 , 即求最小生成樹 [T] 最小生成樹 二、最小生成樹性質 MST 設 N=（ V， {E}）是一個連通網， U是頂點集 V的一個非空子集。 若（ u， v）是一條具有最小權值的邊，其中 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）是連接這兩個頂點集的最小權 值邊，則邊（ u， v）必然是某最小生成樹的邊。 三、普里姆（ Prim）最小生成樹算法 設 N=（ V， {E}）是一個連通網， V={1， 2， … ， n}是 N的頂點集合， 輔助集合 U，初值為 {Uo}， 用來存放當前所得到的最小生成樹的頂點； 輔助集合 TE，初值為 {}， 用來存放當前所得到的最小生成樹的邊。 Prim算法步驟 1. TE=Ф,U={u0} 2. 當 U≠V ，重復下列步驟： (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中的邊構成回路的當前最小代價邊。 特點 : 以最小代價邊為主 設 N=（ V， {E}）是個連通網 , 算法步驟為： 1. 置生成樹 T的初始狀態為 T=（ V， {Ф}） 2. 當 T中邊數 n1時 , 重復下列步驟 : ? 從 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