Prim算法-最小生成树
Prim算法-最小生成树
用户1154259
发布于 2018-01-17 15:23:23
发布于 2018-01-17 15:23:23
基本思想：
1 置S={1}
2 只要S是V的真子集就做如下的贪心选择：
选取满足条件的i ，i属于S，j输入V-S，且c[i][j]最小的边，并将定点j加入S中
这个过程直到S==V为止。
3 这个过程所选的边，恰好就是最小生成树
算法描述：
void Prim(int n,Type * * c)
{
T = 空集;
S = {1};
while(S != V)
{
(i,j)=i 属于 S 且 j属于V-S的最小权边;
T = T∪{(i,j)};
S = S ∪ {j};
}
}模版代码：
template <class Type>
vodi Prim(int n,Type * * c)
{
Type lowcost[maxint];
int closest[maxint];
bool s[maxint];
s[1] = true;
for(int i=2;i<=n;i++)
{
lowcost[i] = c[1][i];
closest[i] = 1;
s[i] = false;
}
for(int i = 1;i<n;i++)
{
Type min = inf;
int j = 1;
for(int k = 2;k <= n;k++)
if((lowcost[k]<min) && (!s[k]))
{
min = lowcost[k];
j=k;
}
cout<<j<<' '<<closest[j]<<endl;
s[j] = true;
for(k = 2;k<= n;k++)
if((c[j][k]<lowcost[k])&&(!s[k]))
{
lowcost[k] = c[j][k];
closest[k] = j;
}
}
}本文参与?腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2012-10-20 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读