最小生成樹and最短路徑(已修改)
2025-07-05 18:52 本頁面
【正文】 最小生成樹and最短路徑無獨有偶，在兩個學期的期末中兩門不同的科目《離散數學》和《數據結構》中都談到了圖及其衍生的最小生成樹、最短路徑問題，并給出了相應的算法——克魯斯卡爾、普林、迪杰斯特拉、沃舍爾算法。這無疑是釋放了一個很大的信號——這些內容很重要。由于之前學《離散數學》時只要求在思想上理解，并沒要求程序實現，所以學起來也挺吃力的。而現在來到了《數據結構》的課程上，我覺得還是有必要寫寫理解與體會，好讓以后用起來沒那么難。最小生成樹（Minimum Spanning Tree,MST ）一個有 n 個結點的連通圖的生成樹是原圖的極小連通子圖，且包含原圖中的所有 n 個結點，并且有保持圖連通的最少的邊。即是在原圖上刪除邊，直到剩余n1條邊，保證n個結點連通且邊的權值加起來最小。簡單圖示：21 121 1 3 2 MST 2 54343 4 4 克魯斯卡爾（Kruskal）算法克魯斯卡爾算法從邊的角度來解決問題，即在剩下的所有未選取的邊中，找最小邊，如果和已選取的邊構成回路，則放棄，選取次小邊。然而，圖的存貯結構采用邊集數組，且權值相等的邊在數組中排列次序可以是任意的，該方法對于邊數相對比較多的圖不是很實用，浪費時間?？梢哉f克魯斯卡爾算法是很直觀的算法，適合人的直觀思考方式，但是因為上面論述的緣故，克魯斯卡爾算法比較適用在稀疏圖（邊的數目不是很多的圖）上。邊集數組：從圖變?yōu)槌绦蛐枰臄祿?，需要采用合適的數據結構。由算法的核心思想上看，我們需要存儲的數據為邊，而邊的要素包括三點：連接的兩個結點、邊的權值。然而邊并不需要具有什么操作來改變自身或者做些什么，所以用struct來自定義就合適不過了。struct edge{ int node_1。 int node_2。 int value 。}。 另外，文中提
電大資料相關推薦
鄂ICP備17016276號-1