算法思想:
1 将G的n个顶点看成n个孤立的连通分支,所有的边按权从小到大排序
2 当查看到第k条边时,
如果断点v和w分别是当前的两个不同的连通分支t1和t2中的顶点时,就用边(v,m)j将t1,t2连接成一个连通分支,然后继续查看第k+1条边;
如果端点v和w当前的同一个连通分支中,就直接查看第k+1条边
实现代码:
template <class Type>
class EdgeNode{
friend ostream& operator<<(ostream&,EdgeNode<Type>);
friend bool Kruskal(int,int,EdgeNode<Type> *,EdgeNode<Type> *);
friend void main(void);
public:
operator Type() const{return weight;}
private:
Type weight;
int u,v;
};
template <class Type>
bool Kruskal(int n,int e,EdgeNode<Type> E[],EdgeNode <Type> t[])
{
MinHeap<EdgeNode<Type>> H(1);
H.Initialize(E,e,e);
UnionFind U(n);
int k = 0;
while(e && k<n-1)
{
EdgeNode<int> x;
H.DeleteMin(x);
e--;
int a = U.Find(x.u);
int b = U.Find(x.v);
if(a != b)
{
t[k++] = x;
U.Union(a,b);
}
}
H.Deactivate();
return (k == n-1);
}