工學(xué)期末復(fù)習(xí)題ppt課件(參考版)
2025-01-20 07:46本頁面
【正文】 最小生成樹 步驟 (v, u) E T 6 (2, 3) ② ① ④ ⑤ ③ 6 6 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ 邊數(shù) =n1=5 代價(jià) =15 。 最小生成樹 ② ① ④ ⑤ 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 ⑥ ② ① ④ ⑤ ③ ⑥ 167。 最小生成樹 167。 特點(diǎn) : 以最小代價(jià)邊主 ， O(eloge)，適合求稀疏的網(wǎng)的最小生成樹 設(shè) N=（ V， {E}）是個(gè)連通網(wǎng) , 算法步驟為： 1. 置生成樹 T的初始狀態(tài)為 T=（ V， {Ф}） 2. 當(dāng) T中邊數(shù) n1時(shí) , 重復(fù)下列步驟 : ? 從 E中選取代價(jià)最小的邊（ v, u） , 并刪除之 。 最小生成樹 Prim算法步驟 1. TE=Ф,U={u0} 2. 當(dāng) U≠V， 重復(fù)下列步驟： (1)選?。?u0,v0)=min{cost(u,v)|u∈ U,v∈ VU}，保證不形成回路 (2)TE=TE+（ u0,v0), 邊（ u0,v0)并入 TE (3)U=U+{V0}， 頂點(diǎn) 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步： 特點(diǎn) : 以連通為主 選代價(jià)最小的鄰接邊 167。 最小生成樹 普里姆（ Prim）最小生成樹算法 設(shè) N=（ V， {E}）是一個(gè)連通網(wǎng)， V={1， 2， … ， n}是 N的頂點(diǎn)集合， 輔助集合 U，初值為 {Uo}， 用來存放當(dāng)前所得到的最小生成樹的頂點(diǎn)； 輔助集合 TE，初值為 {}， 用來存放當(dāng)前所得到的最小生成樹的邊。 含義：將頂點(diǎn)分為兩個(gè)不相交的集合 U和 VU， 若邊（ u， v）是連接這兩個(gè)頂點(diǎn)集的最小權(quán) 值邊，則必然存在一棵包含邊（ u， v）的最小生成樹。 圖的遍歷 ?首先訪問指定頂點(diǎn) v0，將 v0作為當(dāng)前頂點(diǎn) ? 訪問當(dāng)前頂點(diǎn)的所有未訪問過的鄰接點(diǎn)，并 ? 依次將訪問的這些鄰接點(diǎn)作為當(dāng)前頂點(diǎn) ? 重復(fù) 2， 直到所有頂點(diǎn)被訪問為止 0 1 2 3 4 5 6 bfs ( 0 ) 最小生成樹性質(zhì) MST 設(shè) N=（ V， {E}）是一個(gè)連通網(wǎng)， U是頂點(diǎn)集 V的一個(gè)非空子集。 J I F E B D A H G C D B C A BT1 F E BT2 BT3 H J I G 哈夫曼樹及其應(yīng)用 a b c d 7 5 2 4 例 : F={ } a b F={ } c d 7 5 6 2 4 F={ } a b c d 11 6 4 2 5 F={ } a b c d 11 6 4 2 5 7 18 7 （ depthfirstsearch) ~ (stack) ? 訪問指定的某頂點(diǎn) V，將 V作為當(dāng)前頂點(diǎn) ? 訪問當(dāng)前頂點(diǎn)的下一未被訪問過的鄰接點(diǎn)，并以該鄰接點(diǎn)作為當(dāng)前頂點(diǎn) ? 重復(fù) 2，直到所有和當(dāng)前頂點(diǎn)有路徑相通的頂點(diǎn)都被訪問到 ? 沿搜索路徑回退，退到尚有鄰接點(diǎn)未被訪問過的某結(jié)點(diǎn) ? 將該結(jié)點(diǎn)作為當(dāng)前結(jié)點(diǎn)，重復(fù)以上步驟，直到所有頂點(diǎn)被訪問過的為止 0 1 2 3 4 5 6 dfs ( 0 ) 167。 解釋：Ｂ是Ａ的左孩子，Ｃ是Ｂ的右孩子。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1