最小生成樹(shù)之prim算法

算法導(dǎo)論4.6最小生成樹(shù)程勝計(jì)科13-04班問(wèn)題簡(jiǎn)介網(wǎng)絡(luò)G=（V，E）是一個(gè)無(wú)向連通帶權(quán)圖，E中每一條邊（v，w）的權(quán)為c[v][w]。如果G的一個(gè)子圖G’是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G’為G的生成樹(shù)。在G的所有生成樹(shù)中，各邊權(quán)之和最小的稱(chēng)為G的最小生成樹(shù)。Prim算法設(shè)G=（V，E）是連通帶權(quán)圖，V={1,2,….n}.算法的基本思想是：首先置S={1},然后只要S是V的真子集，就做如下貪心選擇：遍歷滿(mǎn)足i∈

S，j∈

V-S的點(diǎn)，找出c[i][j]最小的邊，將頂點(diǎn)加入S中。此過(guò)程一直進(jìn)行到S=V為止，所選取的邊構(gòu)成的就是G的最小生成樹(shù)。void

prim(int

n,

Type**c)

{

Typelowcost[MAX];

int

clost[max];

bools[max];s[1]=true;

for

(i

=

2;

i

<=

n;

i++)

{

lowcost[i]

=

c[1][i];

clost[i]

=

1;

s[i]=false;

}

for

(i

=

1;

i

<n;

i++)

{

Typemin

=

inf;

intj=1;

for

(intk=

2;

k<=

n;

k++)

{

if

(lowcost[k]

<

min

&&

!s[k])

{

min

=

lowcost[k]

j=k;

}

}

cout

<<

“j"

<<

’’<<

closet[j]

<<

endl;

s[j]=true;

for

(intk=

2;

k<=

n;

k++)

{

if

(c[j][k]

<

lowcost[j])

&&(!s[k])

{

lowcost[k]

=

c[j][k];

closet[k]=j;

}

}

}

初始化遍歷鄰近點(diǎn)，找出最短距離的邊，輸出點(diǎn)和邊，并放入S。對(duì)于新加入S的點(diǎn)，通過(guò)比較最短距離，更新lowcost數(shù)組算法過(guò)程詳解算法的核心在兩個(gè)數(shù)組：closet和lowcost。對(duì)于j∈

V-S，closet[j]表示點(diǎn)j與所有S中點(diǎn)的連線(xiàn)中最短的連接點(diǎn)。而lowcost[j]的值就是c[j][closet[j]].在算法的執(zhí)行過(guò)程中，先找出V-S中是lowcost值最小的點(diǎn)，選取邊（j,closet[j]）,將j添加到S中，然后根據(jù)與新加入S的點(diǎn)的距離的比較，更新lowcost數(shù)組。一.初始化在Prim算法中，最小生成樹(shù)的起點(diǎn)設(shè)置為1.此時(shí)S={1}，由于S中只含有點(diǎn)1，故此時(shí)lowcost[i]=c[1][i],Closet[i]=1:Lowcoset[1]=0,

Lowcoset[2]=6,Lowcoset[3]=1,Lowcoset[4]=5,Lowcoset[5]=max,Lowcoset[6]=max,(max表示無(wú)直接連線(xiàn))Example1536243255566641153624二.Lowcost第一次循環(huán)

遍歷lowcost數(shù)組，找到最小值為lowcost[3]=1，所以將點(diǎn)3加入S中，選擇的邊為（1，3）,此時(shí)S={1,3}1536241536241三.更新lowcost數(shù)組前一步將點(diǎn)3加入S，根據(jù)定義，數(shù)組lowcost和closet可能會(huì)發(fā)生改變，需要比較連接點(diǎn)的距離，決定是否更新數(shù)組。C[3][2]=5<6,更新lowcost[2]=5,closet[2]=3;C[3][3]=0;C[3][4]=5=5,不更新；C[3][5]=6<max,更新lowcost[5]=6,clost[5]=3;C[3][6]=4<max,更新lowcost[6]=4,c;ost[6]=3.1536241四.Lowcost數(shù)組第二次循環(huán)由于上一步lowcost數(shù)組更新，故第二次循環(huán)，找出最小值。其中最小值為lowcost[6]=4，將點(diǎn)6添加到S中，此時(shí)S={1,3,6}153624115362414五.Lowcost更新由于新加入點(diǎn)6，根據(jù)定義，數(shù)組lowcost和closet可能會(huì)發(fā)生改變，需要比較連接點(diǎn)的距離，決定是否更新數(shù)組：C[6][2]=max，不更新；C[6][3]=4>1,不更新；C[6][4]=2<5,更新lowcost[4]=2,closet[4]=6;C[6][5]=6=6,不更新；C[6][6]=0,不更新；15362414依此類(lèi)推………153624141536241421536241452