主题:[讨论]图的PRIM算法讨论
/*=======================Prim算法====================================*/
#define MAXINT 9999
#define MAXN 100
int n,u;
/*cost[][]为带权图的邻接矩阵*/
/*n为图的顶点数;u为起始顶点*/
void Prim(int cost[][MAXN],int n,int u)
{
int lowcost[MAXN],n;
int clsest[MAXN]; //顶点序列
int i,j,k;
for(i=1;i<=n;i++) //初始处理
{
lowcost[i]=cost[u][i]; //起始点u到V-U集合中各顶点的权存放在lowcost[]中
closest[i]=u; //将从U的各顶点里到达V-U中各顶点权最小的顶点
}
for(i=1;i<=n;i++) //主循环,若U=V,则算法结束;否则,从E中选一条代价最小的边(u,v),并将u加入U中
{
min=MAXINT;
for(j=1;j<=n;j++) //用选择排序的概念从lowcost[]中找到U到V-U中代价最小的边
if(lowcost[j]!=0&& //该顶点不在U中
lowcost[j]<min) //该到顶点边的权比已经找到的权最小的边还要小
{
min=lowcost[j];
k=j;
}
printf("{%3d %3d %5d}", //打印邻接到U中顶点,权最小的边
closest[k],k,min);
lowcost[k]=0; //将该顶点放入U中,即将lowcost[k]设置为0
for(j=1;j<=n;j++) //U中加入k后,更新lowcost[],重新登记最小权
if(cost[k][j]!=0&&
cost[k][j]<lowcost[j])
{
lowcost[j]=cost[k][j]; //把从U到V-U中各点权最小的边的权记录下来
closest[j]=k; //将到j距离最短距离的顶点更新为k
}
}
}
谁能看看程序中这句的意思?
for(j=1;j<=n;j++) //用选择排序的概念从lowcost[]中找到U到V-U中代价最小的边
if(lowcost[j]!=0&& //该顶点不在U中
lowcost[j]<min) //该到顶点边的权比已经找到的权最小的边还要小
{
min=lowcost[j];
k=j;
}
这里的代码能查到与V相邻的最小权值吗?
#define MAXINT 9999
#define MAXN 100
int n,u;
/*cost[][]为带权图的邻接矩阵*/
/*n为图的顶点数;u为起始顶点*/
void Prim(int cost[][MAXN],int n,int u)
{
int lowcost[MAXN],n;
int clsest[MAXN]; //顶点序列
int i,j,k;
for(i=1;i<=n;i++) //初始处理
{
lowcost[i]=cost[u][i]; //起始点u到V-U集合中各顶点的权存放在lowcost[]中
closest[i]=u; //将从U的各顶点里到达V-U中各顶点权最小的顶点
}
for(i=1;i<=n;i++) //主循环,若U=V,则算法结束;否则,从E中选一条代价最小的边(u,v),并将u加入U中
{
min=MAXINT;
for(j=1;j<=n;j++) //用选择排序的概念从lowcost[]中找到U到V-U中代价最小的边
if(lowcost[j]!=0&& //该顶点不在U中
lowcost[j]<min) //该到顶点边的权比已经找到的权最小的边还要小
{
min=lowcost[j];
k=j;
}
printf("{%3d %3d %5d}", //打印邻接到U中顶点,权最小的边
closest[k],k,min);
lowcost[k]=0; //将该顶点放入U中,即将lowcost[k]设置为0
for(j=1;j<=n;j++) //U中加入k后,更新lowcost[],重新登记最小权
if(cost[k][j]!=0&&
cost[k][j]<lowcost[j])
{
lowcost[j]=cost[k][j]; //把从U到V-U中各点权最小的边的权记录下来
closest[j]=k; //将到j距离最短距离的顶点更新为k
}
}
}
谁能看看程序中这句的意思?
for(j=1;j<=n;j++) //用选择排序的概念从lowcost[]中找到U到V-U中代价最小的边
if(lowcost[j]!=0&& //该顶点不在U中
lowcost[j]<min) //该到顶点边的权比已经找到的权最小的边还要小
{
min=lowcost[j];
k=j;
}
这里的代码能查到与V相邻的最小权值吗?