最小生成树之prim算法

算法导论4.6最小生成树程胜计科13-04班问题简介网络G=（V，E）是一个无向连通带权图，E中每一条边（v，w）的权为c[v][w]。如果G的一个子图G’是一棵包含G的所有顶点的树，则称G’为G的生成树。在G的所有生成树中，各边权之和最小的称为G的最小生成树。Prim算法设G=（V，E）是连通带权图，V={1,2,….n}.算法的基本思想是：首先置S={1},然后只要S是V的真子集，就做如下贪心选择：遍历满足i∈

S，j∈

V-S的点，找出c[i][j]最小的边，将顶点加入S中。此过程一直进行到S=V为止，所选取的边构成的就是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数组算法过程详解算法的核心在两个数组：closet和lowcost。对于j∈

V-S，closet[j]表示点j与所有S中点的连线中最短的连接点。而lowcost[j]的值就是c[j][closet[j]].在算法的执行过程中，先找出V-S中是lowcost值最小的点，选取边（j,closet[j]）,将j添加到S中，然后根据与新加入S的点的距离的比较，更新lowcost数组。一.初始化在Prim算法中，最小生成树的起点设置为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第一次循环

遍历lowcost数组，找到最小值为lowcost[3]=1，所以将点3加入S中，选择的边为（1，3）,此时S={1,3}1536241536241三.更新lowcost数组前一步将点3加入S，根据定义，数组lowcost和closet可能会发生改变，需要比较连接点的距离，决定是否更新数组。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数组第二次循环由于上一步lowcost数组更新，故第二次循环，找出最小值。其中最小值为lowcost[6]=4，将点6添加到S中，此时S={1,3,6}153624115362414五.Lowcost更新由于新加入点6，根据定义，数组lowcost和closet可能会发生改变，需要比较连接点的距离，决定是否更新数组：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