首页 > 代码库 > kruskal 算法模板

kruskal 算法模板

2024-07-15 14:13:19   213人阅读

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2896

 

#include <stdio.h>#include <string.h>#include <stdlib.h>struct node{    int u,v,w;}q[200001];int bin[50001];int n,m,ans;int cmp(const void *a,const void *b){    struct node *x;    struct node *y;    x = (struct node *)a;    y = (struct node *)b;    return x->w - y->w;}int find(int x){    int r,k,j;    r = x;    while(bin[r]!=r)    r = bin[r];    j = x;    while(j!=r)    {        k = bin[j];        bin[j] = r;        j = k;    }    return r;}void kruskal(){    int i;    for(i = 1;i<=n;i++)    {        bin[i] = i;    }    for(i = 0;i<m;i++)    {        int uu = find(q[i].u);        int vv = find(q[i].v);        if(uu!=vv)        {            bin[uu] = vv;            ans+=q[i].w;        }    }    printf("%d\n",ans);}int main(){    int i,j;    while(~scanf("%d%d",&n,&m))    {        ans = 0;        for(i = 0;i<m;i++)        {            scanf("%d%d%d",&q[i].u,&q[i].v,&q[i].w);        }        qsort(q,m,sizeof(q[0]),cmp);        kruskal();    }    return 0;}

 

 

对于kruskal 算法的理解 ：这个算法，我一直半知半解，知道现在才能够说明白，但也还不够熟练，谈谈我对这个算法的理解。

最小生成树的算法一共学了两种，分别是prim算法和kruskal算法，prim算法是我掌握的最好的算法之一，可或许因此对于prim算法过于依赖，对kruskal算法应用不熟练，导致很多题都不能AC ，现在重新学习一下kruskal算法，kruskal算法是一种加边的算法，适合点特别多的数据，kruskal算法应用并查集的知识，判断是否会形成回路，

还有就是结构体一级排序 两个重难点，

特别写一下cmp函数

int cmp(const void *a,const void *b)

{

　　struct node *x,*y;

　　x = （struct node *)a；

　　y = (struct node *)b; (括号不可少)

　　return x.w-y.w;

}

查找函数也是关键，krusal算法比较简单，可以遍历所有的边，进行判断。

 


联系
我们