Kruskal算法-最小生成树

算法思想：

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算法-最小生成树，如需转载请自行联系原博主。