Kruskal算法

偏执的太偏执、 2023-07-08 02:49 22阅读 0赞

/* * Kruskal算法求解最小生成树 * 适用于点多边少的情况 * */
    #include "cstdio"
    #include "algorithm"
    
    using namespace std;
    const int MAXV = 110;
    const int MAXE = 10010;
    //边集定义部分
    struct edge { 
        int u, v;//边的两个端点编号
        int cost;//边权
    } E[MAXE];
    
    bool cmp(edge a, edge b) { 
        //从小到大排序rr
        return a.cost < b.cost;
    
    }
    
    //并查集
    int father[MAXV];
    
    int findFather(int x) { 
        int a = x;
        //寻找根节点
        while (x != father[x]) { 
            x = father[x];
        }
        //此时根节点为x
        //路径压缩
        while (a != father[a]) { 
            int z = a;
            a = father[a];
            //统一根节点
            father[z] = x;
    
        }
    }
    
    //求最小生成树边权和
    int Kruskal(int n, int m) { 
        //n为顶点数,m为图的边树,num为边权和 Num_Edge 为当前生成树边树
        int ans = 0, Num_Edge = 0;
        for (int i = 0; i < m; i++) { 
            father[i] = i;//并查集初始化
        }
        sort(E, E + m, cmp);
        for (int i = 0; i < m; i++) { 
            int faU = findFather(E[i].u);
            int faV = findFather(E[i].v);
            if (faU != faV) { 
                //如果两个顶点不在一个集合
                father[faU] = faV; //合并集合
                ans += E[i].cost;
                Num_Edge++;
                if (Num_Edge == n - 1)
                    break;//边数等于顶点数减一时结束算法
            }
        }
        if (Num_Edge < n - 1)
            return -1; //无法连通
        else return ans;
    }
    
    int main() { 
        int n, m;
        scanf("%d%d", &n, &m);//顶点数 边数
        for (int i = 0; i < m; i++) { 
            scanf("%d%d%d", &E[i].u, &E[i].v, &E[i].cost);
    
        }
        int ans = Kruskal(n, m);
        printf("%d\n", ans);
        return 0;
    
    }
    /*测试数据 6 10 0 1 4 0 4 1 0 5 2 1 2 1 1 5 3 2 3 6 2 5 5 3 4 5 3 5 4 4 5 3 */

测试结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2020022420351532.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5ODI3Njc3,size_16,color_FFFFFF,t_70