最小生成树2（Kruskal算法）

浏览数：12 / 时间：2015年06月08日

Kruskal算法：

1：按照边的权值的顺序从小到大查看一遍，如果不产生圈（重边也算），就把当前这条边加入到生成树中，基本算法证明和prim一样

2：如何判断是否产生负圈，假设现在要把连接顶点u和顶点v的边e加入到生成树中，如果加入之前u和v不在同一个联通分量里，那么加入e也不会产生负圈，反之，如果u和v在同一个连通分量里，那么一定会产生圈，可以使用并查集高效的判断是否属于同一个连通分量

PS：Kruskal算法耗时在于其对边的排序，算法复杂度为O（|E|log|V|）

struct node
{
    int u,v,w;
} edge[max_v*max_v];

bool cmp(node a,node b)
{
    if(a.w<=b.w) return true;
    return false;
}
int find(int x)
{
    if(x!=father[x]) return find(father[x]);
     return x;
}
int kruskal(int n,int m)
{
    sort(edge,edge+m,cmp);
    int x,y,res=0;
    for(int i=0; i<m; i++)
    {
        x=edge[i].u;
        y=edge[i].v;
        x=find(x);
        y=find(y);
        if(x!=y)
        {
            res+=edge[i].w;
            father[y]=x;
        }
    }
    return res;
}

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

最小生成树2（Kruskal算法）