資料內(nèi)容:
最小生成樹(Minimum Spanning Tree, MST)
最小生成樹是一個無向加權(quán)連通圖的子集,它連接了圖中的所有頂點(節(jié)點),并且沒有循環(huán)(回路),同
時所有邊的權(quán)重之和是最小的。在計算機(jī)網(wǎng)絡(luò)、電路設(shè)計、物流運輸?shù)阮I(lǐng)域有著廣泛的應(yīng)用。
Prim算法實現(xiàn)原理和步驟
1. 從一個頂點開始,將其加入已選擇的頂點集合。
2. 找出所有與已選擇的頂點集合相鄰的、且未選擇的頂點中權(quán)重最小的邊。
3. 將該邊加入最小生成樹,并將該邊的另一端點加入已選擇的頂點集合。
4. 重復(fù)步驟2和3,直到所有頂點都被選擇。