kruskal算法 订阅
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树 [1]  。 展开全文
克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树 [1]  。
信息
目    的
用来查找最小生成树 [1]
应用领域
数理科学 [1]
外文名
Kruskal algorithm [2]
中文名
克鲁斯卡尔算法 [1]
类似算法
普里姆算法 [1]
学    科
运筹学 [1]
克鲁斯卡尔算法基本思想
克鲁斯卡尔(Kruskal)算法从另一途径求网的最小生成树。其基本思想是:假设连通网G=(V,E),令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点分别在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边而选择下一条代价最小的边。依此类推,直至T中所有顶点构成一个连通分量为止 [2]  。
收起全文
精华内容
下载资源
问答
  • Kruskal算法

    2020-03-31 10:11:20
    Kruskal算法

    Kruskal算法

    展开全文
  • kruskal算法

    2015-07-25 14:39:04
    matlab kruskal算法 求最小生成树
  • KRUSKAL算法

    2012-07-03 16:31:59
    kruskal算法的实现 通过生成一个最小生成树
  • Kruskal 算法

    2019-08-02 12:46:24
    - Kruskal 算法 - Kruskal 算法Kruskal 算法总是维护无向图的最小生成森林。最初,可认为生成森林由零条边构成,每个节点各自构成一棵仅包含一个点的树。在任意时刻,Kruskal 算法从剩余的边中选出一条权值最小...

    - Kruskal 算法 -

    Kruskal 算法:

    Kruskal 算法总是维护无向图的最小生成森林。最初,可认为生成森林由零条边构成,每个节点各自构成一棵仅包含一个点的树。在任意时刻,Kruskal 算法从剩余的边中选出一条权值最小的,并且这条边的两个端点属于生成森林中两棵不同的树(不连通),把该边加入生成森林。图中节点的连通情况可以用并查集维护。

    复杂度:

    时间复杂度:O(nlogn)

    算法过程:

    1、建立并查集,每个点各自构成一个集合;
    2、把所有边按照权值从小到大排序,依次扫描每条边(x,y,z);
    3、若 x,y 属于同一集合(连通),则忽略这条边,继续扫描下一条;
    4、否则,合并 x,y 所在的集合,并把 z 累加到答案中;
    5、所有边扫描完成后,第4步中处理过的边就构成最小生成树。

    int par[N];
    struct node{
        int from;//边的起点
        int w;//边的权值
        int to;//边的终点
    }edge[N*N];
    
    bool cmp(node x, node y) {
        return x.w<y.w;
    }
    
    void init(int n) {//并查集
        for(int i=1; i<=n; i++) {
            par[i]=i;//父亲
        }
    }
    
    int find(int a) {
        if(par[a]==a) return a;
        else return par[a]=find(par[a]);
    }
    
    void kruskal(int cnt, int n) {//cnt表示待扫描的边的数目,n表示所有节点的数目
        sort(edge, edge+cnt, cmp);
        int ans=0, num=0;
        for(int i=0; i<cnt; i++) {
            if(num==n-1) break;//已得到最小生成树跳出循环
            int a=find(edge[i].from), b=find(edge[i].to);
            if(a!=b) {
                par[b]=a;//合并a,b集合
                ans+=edge[i].w;
                num++;
            }
        }
        printf("%d\n", ans);
        return ;
    }

    例题:

    - HDU 1102 -

    Constructing Roads

    Time Limit: 2000/1000 MS (Java/Others) | Memory Limit: 65536/32768 K (Java/Others)

    题意:

    给定一个整数 n ,表示村庄数(从1~n编号),接下来 n 行,每行 n 个整数,第 i 行第 j 列的数表示村庄 i 和 村庄 j 之间的距离,然后给定一个整数 q ,接下来 q 行每行有两个数a,b,表示村庄 a、b 之间的路已连通,最后求使得所有村庄互相连通需要修的最短的路。

    数据范围:

    N (3 <= N <= 100),村庄之间的距离在 [ 1, 1000 ] 范围内,Q (0 <= Q <= N * (N + 1) / 2), (1 <= a < b <= N)

    解题思路:

    Prime 算法 or Kruskal 算法 以下选择用 Kruskal 算法实现
    用 Prime 算法实现的代码链接–>- Prime 算法 -

    代码:

    #include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    #include <stack>
    #include <queue>
    #include <vector>
    #include <map>
    using namespace std;
    #define INF 0x3f3f3f
    
    typedef long long ll;
    const int N=105;
    int par[N], rankk[N];
    
    struct node{
        int from;//边的起点
        int w;//边的权值
        int to;//边的终点
    }edge[N*N];
    
    bool cmp(node x, node y) {
        return x.w<y.w;
    }
    
    void init(int n) {//并查集
        for(int i=1; i<=n; i++) {
            par[i]=i;//父亲
            rankk[i]=0;//树的高度
        }
    }
    
    //这里合并a,b集合时采用了把更低的树合并到更高的树的方法,虽然可以缩短查找节点的根的时间,但是rankk数组会占用较大内存,如果不会超时的话,其实可以不用那么麻烦,直接令par[b]=a就可以了
    void unite(int a, int b) {//并查集
        if(rankk[a]<rankk[b])
            par[a]=b;
        else {
            par[b]=a;
            if(rankk[a]==rankk[b])
                rankk[a]++;
        }
        return ;
    }
    
    int find(int a) {
        if(par[a]==a) return a;
        else return par[a]=find(par[a]);//这一步很重要,把节点直接连到根节点上,能大大缩短查找根节点的时间
    }
    
    void kruskal(int cnt, int n) {//cnt表示待扫描的边的数目,n表示所有节点的数目
        sort(edge, edge+cnt, cmp);
        int ans=0, num=0;
        for(int i=0; i<cnt; i++) {
            if(num==n-1) break;
            int a=find(edge[i].from), b=find(edge[i].to);
            if(a!=b) {
                unite(a, b);
                ans+=edge[i].w;
                num++;
            }
        }
        printf("%d\n", ans);
        return ;
    }
    
    int main() {
        int n, cnt;
        while(scanf("%d", &n)!=EOF) {
            init(n);
            cnt=0;
            for(int i=1; i<=n; i++) {
                for(int j=1; j<=n; j++) {
                    scanf("%d", &edge[cnt].w);
                    edge[cnt].from=i;
                    edge[cnt].to=j;
                    cnt++;
                }
            }
            int q, a, b;
            scanf("%d", &q);
            while(q--) {
                scanf("%d %d", &a, &b);
                edge[cnt].from=a;
                edge[cnt].to=b;
                edge[cnt].w=0;
                cnt++;
            }
            kruskal(cnt, n);
        }
        return 0;
    }
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 25,460
精华内容 10,184
关键字:

kruskal算法