回 帖 发 新 帖 刷新版面

主题:[讨论]图的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相邻的最小权值吗?

回复列表 (共1个回复)

沙发

注释里不是说的很明白了么……

我来回复

您尚未登录,请登录后再回复。点此登录或注册