以下是我从网上看到的最小生成树的算法

struct node
{
    int beg, end, weight;
} edge[maxn];//边的数组
node EDGE(int a, int b, int w)
{
    node e;
    e.beg = a, e.end = b, e.weight = w;
    return e;
}//类构造函数   
bool cmp(node a, node  b)
{
    return a.weight < b.weight;
} //边排序的时候的比较函数，以边权较小优先 
int uset[maxn];//以下为并查集
int root(int v)
{
    if(uset[v] == v) return v;
    else
    {
        uset[v] = root(uset[v]);
        return uset[v];
    }
}
inline bool same(int a, int b)
{
    return root(a) == root(b);
}
inline void unite(int a,int b)
{
    if(same(a, b) ) return;
    uset[uset] = uset[a];
}

int kruskal(int N, int E)
{//接口：N：顶点个数，E：边的个数
    sort(edge, edge + E, cmp);//对边的数组排序
    int i, ct(0);
    for(i = 0; i <= N; i++)
       uset = i;//并查集初始化
    int ans(0);
    for(i = 0; i < E; i++)
    {
        if(same(edge.beg, edge.end) ) continue;
        ct++;
        if(ct == N) break;//找到N - 1条边之后就可以结束算法
        unite(edge.beg, edge.end);
        ans += edge.weight;
    }  
    return ans;
}