图论浅析--最小生成树之Kruskal

Kruskal

算法思想

1. 将带权图G的所有边按权值从小到大排序；
2. 图G’初始为空；
3. 从小到大取边；
4. 若加入边(x,y)，G’中有环，则放弃此边，继续取边；
5. 将边(x,y)加入图G’中，直至加入n-1条边。

过程演示

Code

struct Edge
{
    int u,v,w;
}e[NUM];
int n;
int f[NUM];//并查集使用
int tol;//边数，加边前赋值为0

bool cmp(Edge a,Edge b){return a.w<b.w;}

int find(int x)
{
    if(f[x]==-1) return x;
    else return f[x]=find(f[x]);
}

void addedge(int u,int v,int w)
{
    e[tol].u=u;
    e[tol].v=v;
    e[tol++].w=w;
}

int Kruskal()
{
    memset(f,-1,sizeof(f));
    int cnt=0;//计算加入的边数
    int ans=0;

    sort(e,e+tol,cmp);
    for(int i=0; i<tol; i++)
    {
        int u=e[i].u;
        int v=e[i].v;
        int w=e[i].w;
        int t1=find(u);
        int t2=find(v);
        if(t1!=t2)
        {
            ans+=w;
            f[t1]=t2;
            cnt++;
        }
        if(cnt==n-1)break;
    }
    if(cnt<n-1) return -1;//不连通
    else return ans;
}