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