《數據結構（C語言描述）（第2版）》教學課件5-11普里姆算法執行過程_第1頁
《數據結構（C語言描述）（第2版）》教學課件5-11普里姆算法執行過程_第2頁
《數據結構（C語言描述）（第2版）》教學課件5-11普里姆算法執行過程_第3頁
《數據結構（C語言描述）（第2版）》教學課件5-11普里姆算法執行過程_第4頁
《數據結構（C語言描述）（第2版）》教學課件5-11普里姆算法執行過程_第5頁
已閱讀5頁，還剩9頁未讀， 繼續免費閱讀

下載本文檔

版權說明：本文檔由用戶提供并上傳，收益歸屬內容提供方，若內容存在侵權，請進行舉報或認領

文檔簡介

1、2016數據結構Data structure講授：劉斌普里姆算法執行過程常州信息職業技術學院02教學目標1普里姆算法求最小生成樹的過程03三、鏈表的插入04普里姆算法執行過程1.1V0V3V1V5V4V25626364751普里姆算法求最小生成樹 對圖5-16的連通網G10，使用普里姆算法求最小生成樹T的執行過程如圖5-17(a)(i)。其中：用實線表示屬于TE的邊，實線邊的兩個頂點均屬于U，虛線表示不屬于TE的邊，虛線邊的兩個頂點一端屬于U，另一端屬于V-U。圖5-16 連通網G1005普里姆算法執行過程1.1普里姆算法求最小生成樹將頂點v0到各頂點的邊及權值放入數組Edge中，并將v0加入

2、U中。此時，U=v0，TE=，Edge0=(v0,v0,0)，Edge1=(v0,v1,6)，Edge2=(v0,v2,1)，Edge3=(v0,v3,5)，Edge4=(v0,v4,)，Edge5=(v0,v5,)V0V3V1V5V4V256（a）1V0V3V1V5V4V2562636475106普里姆算法執行過程1.1在Edge中查找最小權值的邊得到Edge2，k=2，即邊(v0,v2,1)，將該邊加入TE，頂點G-vexsk加入U，此時U=v0,v2，TE=(v0,v2,1)，Edge2=(v0,v2, 0)，其它元素未變。V0V3V1V5V4V256（b）0普里姆算法求最小生成樹V0V

3、3V1V5V4V2562636475107普里姆算法執行過程1.1 新頂點v2加入U后，調整數組Edge。由于頂點v2到頂點v1的權值為5，比頂點v0到頂點v1的權值小，所以將Edge1=(v0,v1,6) 調整為Edge1=(v2,v1, 5)，同樣將Edge4=(v0,v4,)，Edge5=(v0,v5,)分別調整為Edge4=(v2,v4,6)，Edge5=(v2,v5,4) ，而頂點v2到頂點v3的權值為7，不比頂點v0到頂點v3的權值小，所以無需調整Edge3=(v0,v3,5)，調整后的情況為：Edge0=(v0,v0,0)，Edge1=(v2,v1,5)，Edge2=(v0,v2

4、,0)，Edge3=(v0,v3,5)，Edge4=(v2,v4,6)，Edge5=(v2,v5,4)。V0V3V1V5V4V255（c）640V0V3V1V5V4V2562636475108普里姆算法執行過程1.1再在Edge中查找最小權值的邊得到Edge5，k=5，即邊(v2,v5,4)，將該邊加入TE，頂點G-vexsk加入U，此時U=v0,v2,v5，TE=(v0,v2,1), (v2,v5,4)， Edge5=(v2,v5, 0)，其它元素未變。V0V3V1V5V4V255（d）600普里姆算法求最小生成樹V0V3V1V5V4V2562636475109普里姆算法執行過程1.1新頂點

5、v5加入U后，調整數組Edge。由于頂點v5到頂點v3的權值為2，比頂點v0到頂點v3的權值小，所以將Edge3=(v0,v3,5) 調整為Edge3=(v5,v3, 2)，其它均無需調整，調整后的情況為：Edge0=(v0,v0,0)，Edge1=(v2,v1,5)，Edge2=(v0,v2,0)，Edge3=(v5,v3,2)，Edge4=(v2,v4,6)，Edge5=(v2,v5,0)。V0V3V1V5V4V225（e）600V0V3V1V5V4V2562636475110普里姆算法執行過程1.1再在Edge中查找最小權值的邊得到Edge3，k=3，即邊(v5,v3,2)，將該邊加入T

6、E，頂點G-vexsk加入U，此時U=v0,v2,v5,v3，TE=(v0,v2,1), (v2,v5,4) , (v5,v3,2)，Edge3=(v5,v3, 0)，其它元素未變。如圖5-17(f)。新頂點v3加入U后，無需調整數組Edge。 V0V3V1V5V4V205（f）600V0V3V1V5V4V25626364751三、鏈表的插入11普里姆算法執行過程1.1再在Edge中查找最小權值的邊得到Edge1，k=1，即邊(v2,v1,5)，將該邊加入TE，頂點G-vexsk加入U，此時U=v0,v2,v5,v3,v1，TE=(v0,v2,1), (v2,v5,4) , (v5,v3,2)

7、 , (v2,v1,5)，Edge1=(v2,v1, 0)，其它元素未變。V0V3V1V5V4V200（g）600普里姆算法求最小生成樹V0V3V1V5V4V2562636475112普里姆算法執行過程1.1新頂點v1加入U后，調整數組Edge。由于頂點v1到頂點v4的權值為3，比頂點v2到頂點v4的權值小，所以將Edge4=(v2,v4,6) 調整為Edge4=(v1,v4, 3)，其它均無需調整，調整后的情況為：Edge0=(v0,v0,0)，Edge1=(v2,v1,0)，Edge2=(v0,v2,0)，Edge3=(v5,v3,0)，Edge4=(v1,v4,3)，Edge5=(v2,v5,0)。V0V3V1V5V4V200（h）300V0V3V1V5V4V2562636475113普里姆算法執行過程1.1 再在Edge中查找最小權值的邊得到Edge4，k=4，即邊(v1,v4,3)，將該邊加入TE，頂點G-vexsk加入U，此時U=v0,v2,v5,v3,v1,v4，TE=(v0,v2,1), (v2,v5,4) , (v5,v3,2

溫馨提示

  • 1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙，網頁內容里面會有圖紙預覽，若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間，僅對用戶上傳內容的表現方式做保護處理，對用戶上傳分享的文檔內容本身不做任何修改或編輯，并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容，請與我們聯系，我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論