圖與網(wǎng)絡(luò)分析ppt課件(2)-資料下載頁
2025-05-06 23:01本頁面
【正文】 6 3 5 4 3 2 ?將邊按權(quán)從小到大排序 ( v2,v3),( v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4), (v3,v6),(v3,v4),(v1,v3),(v1,v2) ?將邊加入到新圖中 ,如不構(gòu)成回路則保留 。否則 ,去掉 . 例：求下圖的一棵最小支撐樹 ( v2,v3),( v4,v5),(v6,v7),(v4,v6),(v5,v7),(v2,v5),(v5,v6),(v2,v4), (v3,v6),(v3,v4),(v1,v3),(v1,v2) v1 v2 v3 v4 v5 v6 v7 8 7 1 4 5 6 5 4 3 2 2 3 其權(quán)為： 19 定理 8 用 Kruskal算法得到的子圖 T*＝(e1,e2,…,e n1)是一棵最小樹。 算法 2（破圈法） （ 1）從圖 G中任選一棵樹 T1。 （ 2）加上一條弦 e1， T1+e1中立即生成一個圈。去掉此圈中最大權(quán)邊，得到新樹 T2。以 T2代 T1，重復(fù)（ 2）再檢查剩余的弦，直到全部弦檢查完畢為止。 例：用破圈法求上圖中的一棵最小生成樹。 定理 9 圖 G的生成樹 T為最小樹，當(dāng)且僅當(dāng)對任一 e來說， e是 T+e中與之對應(yīng)的圈 ?e中的最大權(quán)邊。 四、根樹及其應(yīng)用 定義 17 若一個有向圖在不考慮邊的方向時是一棵樹，則稱這個有向圖為 有向樹 。 定義 18 有向樹 T，恰有一個結(jié)點入次為 0，其余各點入次均為 1，則稱 T為 根樹 （又稱外向樹）。根樹中入次為 0的點稱為 根 。根樹中出次為 0的點稱為 葉 ，其他頂點稱為 分枝點 。由根到某一頂點 vi的道路長度（設(shè)每邊長度為1），稱為點 vi的 層次 。 定義 19 在根樹中，若每個頂點的出次小于或等于 m，稱這棵樹為 m叉樹 。若每個頂點的出次恰好等于 m或零 ，則稱這棵樹為 完全 m叉樹 。當(dāng) m=2時，稱為二叉樹、完全二叉樹。 在實際問題中常討論葉子上帶權(quán)的二叉樹。令有 s個葉子的二叉樹 T各葉子的權(quán)分別為 pi，根到各葉子的距離 (層次 )為 li(i＝ 1， … ， s)，這樣二叉樹 T的總權(quán)數(shù) ???siiilpTm1)(滿足總權(quán)最小的二叉樹稱為 最優(yōu)二叉樹 ?；舴蚵?(D A Huffman)給出了一個求最優(yōu)二叉樹的算法，所以又稱 霍夫曼樹 。 算法步驟為： （ 1）將 s個葉子按權(quán)由小至大排序，不失一般性，設(shè) p1≤p2 ≤ … ≤ p s。 （ 2）將二個具有最小權(quán)的葉子合并成 一個分枝點，其權(quán)為 p1+p2，將新的分枝點作為一個葉子。令 s?s1，若 s＝ 1停止，否則轉(zhuǎn)（ 1） 例 8 S=6，其權(quán)分別為 4,3,3,2,2,1，求最優(yōu)二叉樹。 例 9 最優(yōu)檢索問題。 使用計算機(jī)進(jìn)行圖書分類?，F(xiàn)有五類圖書共 l00萬冊，其中有 A類 50萬冊， B類 20萬冊， C類 5萬冊， D類 l0萬冊， E類 15萬冊。問如何安排分檢過程，可使總的運算（比較）次數(shù)最小 ?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1