最小生成樹之prim算法

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

S，j∈

V-S的點，找出c[i][j]最小的邊，將頂點加入S中。此過程一直進行到S=V為止，所選取的邊構(gòu)成的就是G的最小生成樹。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;

}

}

}

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

V-S，closet[j]表示點j與所有S中點的連線中最短的連接點。而lowcost[j]的值就是c[j][closet[j]].在算法的執(zhí)行過程中，先找出V-S中是lowcost值最小的點，選取邊（j,closet[j]）,將j添加到S中，然后根據(jù)與新加入S的點的距離的比較，更新lowcost數(shù)組。一.初始化在Prim算法中，最小生成樹的起點設(shè)置為1.此時S={1}，由于S中只含有點1，故此時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表示無直接連線)Example1536243255566641153624二.Lowcost第一次循環(huán)

遍歷lowcost數(shù)組，找到最小值為lowcost[3]=1，所以將點3加入S中，選擇的邊為（1，3）,此時S={1,3}1536241536241三.更新lowcost數(shù)組前一步將點3加入S，根據(jù)定義，數(shù)組lowcost和closet可能會發(fā)生改變，需要比較連接點的距離，決定是否更新數(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，將點6添加到S中，此時S={1,3,6}153624115362414五.Lowcost更新由于新加入點6，根據(jù)定義，數(shù)組lowcost和closet可能會發(fā)生改變，需要比較連接點的距離，決定是否更新數(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依此類推………153624141536241421536241452