prim算法(自主理解)
代码:
void Prim(MatGraph g,int v)
{
int lowcost[MAXV];
int closest[MAXV];
int MIN;
int i,j,k;
for(i=0;i<g.n;i++)
{
lowcost[i]=g.edges[v][i];
closest[i]=v;
}
for(i=1;i<g.n;i++)
{
MIN=INF;
for(j=0;j<g.n;j++)
{
if(lowcost[j]!=0&&lowcost[j]<MIN)
{
MIN=lowcost[j];
k=j;
}
}
printt("边为(%d,%d)权值为:%d\n",closest[k],k,MIN);
lowcost[k]=0;
for(j=0;j<g.n;j++)
{
if(lowcost[j]!=0&&g.edges[k][j]<lowcost[j])
{
lowcost[j]=g.edges[k][j];
closest[j]=k;
}
}
}
} 图解:
