掌握Prim算法的特點(diǎn)，學(xué)會(huì)用Prim算法構(gòu)造最小生成樹(shù) 如果無(wú)向連通圖是一個(gè)網(wǎng)，那么它的所有生成樹(shù)中必有一棵樹(shù)的邊的權(quán)值總和為最小，我們稱這棵生成樹(shù)為最小生成樹(shù)。在Prim算法中，在圖G=(V,E)（V表示頂點(diǎn)，E表示邊）中任選一點(diǎn)V0，令集合U={V0}為初態(tài)，從V0出發(fā)尋找與U中頂點(diǎn)相鄰（另一頂點(diǎn)在V中）且代價(jià)最小的邊的另一頂點(diǎn)V1，并使V1加入U(xiǎn)，即U={V0，V1}，同時(shí)（V0，V1）邊加入集合T中（T的初態(tài)為空），這樣不斷地?cái)U(kuò)大U,直到U=V，則T中即為最小生成樹(shù)的邊。

點(diǎn)擊標(biāo)簽查看更多相關(guān)資源：