kruskal最小生成树.cpp

最小生成树的几种算法的实现

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[b]] = 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] = i;//并查集初始化 
    int ans(0);
    for(i = 0; i < E; i++)
    {
        if(same(edge[i].beg, edge[i].end) ) continue;
        ct++;
        if(ct == N) break;//找到N - 1条边之后就可以结束算法 
        unite(edge[i].beg, edge[i].end);
        ans += edge[i].weight;
    }   
    return ans;
}