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