算法思想：
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); }
本文转自博客园xingoo的博客，原文链接：Kruskal算法-最小生成树，如需转载请自行联系原博主。
