45-伪代码详解

2.7.4　伪代码详解

（1）初始化。s[1]=true，初始化数组closest，除了u₀外其余顶点最邻近点均为u₀，表示V−U中的顶点到集合U的最临近点均为u₀；初始代数组lowcost，u₀到V−U中的顶点的边值，无边相连则为∞（无穷大）。

s[u0] = true; //初始时，集合中U只有一个元素，即顶点u0
for(i = 1; i <= n; i++) 
{
     if(i != u0) //除u0之外的顶点
     {
          lowcost[i] = c[u0][i];   //u0到其它顶点的边值
          closest[i] = u0;  //最邻近点初始化为u0
          s[i] = false;  //初始化u0之外的顶点不属于U集合，即属于V-U集合
     }
      else
          lowcost[i] =0;
}

（2）在集合V−U中寻找距离集合U最近的顶点t。

int temp = INF;
int t = u0;
for(j = 1; j <= n; j++) //在集合中V-U中寻找距离集合U最近的顶点t
{
    if((!s[j]) && (lowcost[j] < temp)) //!s[j] 表示j结点在V-U集合中
    { 
        t = j;
        temp = lowcost[j];
    }
}
if(t == u0) //找不到t，跳出循环
   break;

（3）更新lowcost和closest数组。

s[t] = true;     //否则，讲t加入集合U
for(j = 1; j <= n; j++)  //更新lowcost和closest
{
    if((!s[j]) && (c[t][j] < lowcost[j])) // !s[j] 表示j结点在V-U集合中
                                          //t到j的边值小于当前的最邻近值
    {
         lowcost[j] = c[t][j]; //更新j的最邻近值为t到j的边值
         closest[j] = t;    //更新j的最邻近点为t
    }
}