一个连通图的生成树是一个极小连通子图，它包括图中全部顶点，并且有尽可能少的边。一棵生成树的代价是各条边上的代价之和。一个网络的生成树中具有最小代价的生成树称为该网络的最小代价生成树。  

    构造最小代价生成树的两种算法：普里姆算法（Prim)，克鲁斯卡尔算法(Kruskal)

      设G=(V,E)是带权的连通图，T=(V’,E’)是正在构造中的生成树。初始状态下，这棵生成树只有一个顶点，没有边，即V’={v0}，E’={ }，v0是任意选定的起始顶点。

      从初始状态开始，重复执行下列运算：

      在所有u属于V’，v属于V-V’的边(u,v)，(u,v)属于E 中找一条代价最小的边(u’,v’)，边(u’,v’)并入集合E’，将顶点v’并入集合V’。直到V=V’为止。这时E’中必有n-1条边，T=(V’,E’)是图G的一棵最小代价生成树。

算法描述本（采用邻接表存储）：

      为实现Prim算法,定义两个一维数组:nearest, lowcost，用于存放中间构造过程和最终结果。再定义一个一维数组mark，用于表示某个顶点是否在生成树上。

        对于当前尚未入选生成树的顶点v,此时可存在若干条边使它与生成树上顶点相邻接，边(u,v)是其中权值最小者，那么nearest[v]=u，而该最小权值w(u,v)存在lowcost[v]中。

       如果mark[v]=false,表示v未加入生成树，反之，v已选入。

       初始时，nearest[v]=-1，lowcost[v]=INFTY,mark[v]=false.

template<class T>
void ExtLGraph<T >::Prim(int k,int* nearest,T* lowcost)
{
     bool* mark=new bool[n];
     ENode<T> *p;
     if (k<0||k>n-1) throw OutofBounds;
     for (int i=0;i<n;i++){             // 初始化
           nearest[i]=-1;mark[i]=false;
           lowcost[i]=INFTY;
      }
      lowcost[k]=0; nearest[k]=k; mark[k]=true;   
      // 源点k加入生成树 
    for (i=1;i<n;i++){
              for(p=a[k];p;p=p->nextArc){  
              //修改lowcost和nearest的值
	      int j= p->adjVex;
	      if ((!mark[j] )&&(lowcost[j]>p->w)){
	            lowcost[j]=p->w; nearest[j]=k;   
                    }
              }
             T min=INFTY;     //求下一条最小权值的边
             for (int j=0;j<n;j++)   
              //求不属于树中的顶点中，具有最小lowcost的顶点k
                    if ((!mark[j])&&(lowcost[j]<min)){
                          min=lowcost[j]; k=j;
                    }
            mark[k]=true;     //将顶点k加到生成树上
        } 
}