工學(xué)期末復(fù)習(xí)題ppt課件-資料下載頁
2025-01-17 07:46本頁面
【正文】 有最小權(quán)值的邊，其中 u∈ U,v∈ VU, 即（ u， v） =Min{cost(x,y)|x∈ U,y∈ VU} 則必存在一棵包含邊（ u， v）的最小生成樹。 含義：將頂點(diǎn)分為兩個(gè)不相交的集合 U和 VU， 若邊（ u， v）是連接這兩個(gè)頂點(diǎn)集的最小權(quán) 值邊，則必然存在一棵包含邊（ u， v）的最小生成樹。 u vu u’ v u’ v’ 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)前所得到的最小生成樹的邊。 167。 最小生成樹 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。 最小生成樹 克魯斯卡爾（ Kruskal） 最小生成樹算法 Kruskal 算法是逐步給生成樹 T中添加不和 T中的邊構(gòu)成回路的當(dāng)前最小代價(jià)邊。 特點(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） , 并刪除之 。 ? 若（ v, u） 依附的頂點(diǎn) v和 u落在 T中不同的連同分量上， 則將邊（ v, u）并入到 T的邊集中； 否則，舍去該邊，選擇下一條代價(jià)最小的邊 . 167。 最小生成樹 167。 最小生成樹 ② ① ④ ⑤ 5 2 1 ③ 3 4 6 6 5 5 6 ⑥ ② ① ④ ⑤ 5 2 ③ 3 4 6 6 5 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ ② ① ④ ⑤ ③ ⑥ 1 (1, 3) 0 步驟 (v, u) E T 167。 最小生成樹 ② ① ④ ⑤ 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。 最小生成樹 5 (1, 4) 4 (3, 6) ② ① ④ ⑤ 5 ③ 6 6 5 5 6 ⑥ ② ① ④ ⑤ ③ 6 6 5 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ ② ① ④ ⑤ ③ ⑥ 步驟 (v, u) E T 167。 最小生成樹 步驟 (v, u) E T 6 (2, 3) ② ① ④ ⑤ ③ 6 6 5 6 ⑥ ② ① ④ ⑤ ③ ⑥ 邊數(shù) =n1=5 代價(jià) =15
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1