克鲁斯卡尔算法的选边准则是:
在E中选择一条代价最小的边(u,v),并将其从E中删除;
若在T中加入边(u,v)以后不形成回路,则将其加进T中(这就要求u和v分属于生成森林的两棵不同的树上,由于边(u,v)的加入,这两棵树连成一棵树),否则继续选下一条边。
直到E’中包含n-1条边,T=(V,E’)是图G的一棵最小代价生成树。
生成过程
//每条边具有如下定义的结构类型:
template<class T>
struct eNode{
operator T ()const { return w;}
int u,v;
T w;
};
/*********************/
template <class T>
void ExtLGraph<T>::Kruskal(PrioQueue<eNode<T> >& pq)
{ //优先权队列 pq中保存无向图边集
eNode<T> x;
UFSet s(n);
int u,v,k=0;
while (k<n-1 && !pq.IsEmpty()){
pq.Serve(x);
u=s.Find(x.u);
v=s.Find(x.v);
if (u!=v){
s.Union(u,v);
k++;
cout<<"("<<x.u<<","<<x.v<<","<<x.w<<") ";
}
}
if (k<n-2) {
cout<<“NonConnected”;return;
}
}