prim1.cpp

用C++编写的《算法与程序设计》（王晓东版）的书中的数据结构类（全集）

template<class T>
bool AdjacencyWGraph<T>::Prim(EdgeNode<T> *t)
{
  int i,j,k,kk=0;
  T *lowcost = new T [n+1];
  int *closest = new int [n+1];
  bool *s = new bool [n+1];
  s[1]=true;
  for (i = 2; i <= n; i++){
    lowcost[i] = a[i][1];
    closest[i]=1;
    s[i]=false;
    }
  for (i = 1; i < n; i++){
    T min=NoEdge;
    j=1;
    for (k = 2; k <= n; k++)
      if ((lowcost[k]<min)&&(!s[k])){
        min=lowcost[k];
        j=k;}
    if(min==NoEdge)return false;
    t[kk].weight = lowcost[j];
    t[kk].u = j;
    t[kk++].v = closest[j];
    s[j]=true;
    for (k = 2; k <= n; k++)
      if ((a[k][j]<lowcost[k])&&(!s[k])){
        lowcost[k]=a[k][j];
        closest[k]=j;
        }
    }
  return (kk == n-1);
}