最小生成树

最小生成包含两种算法

• Prim O(n ^ 2)
• Kruskal O(mlogm)

Prim

主要分为两种朴素版Prim，堆优化版Prim

朴素版Prim时间复杂度是O(n ^ 2)

堆优化版代码过于复杂建议使用Kruskal

流程

初始化d数组为正无穷

d[1] = 0

for循环迭代n次，找到集合外距离集合最近的点t，然后用t来更新每一个点到起点的距离

最终将t放入到st集合中

int prim() {
    memset(d,0x3f,sizeof(d));
    int res = 0;

    for(int i = 0;i < n;i++) {
        int t = -1;
        for(int j = 1;j <= n;j++) {
            if(!st[j] && (t == -1 || d[t] > d[j])) {
                t = j;
            }
        }

        //如果出现自环的现象，更新其他边的那一步就会出现自己更新自己的情况，但是最小生成树是不用考虑自环的
        if(i && d[t] == 0x3f3f3f3f) return 0x3f3f3f3f;
        if(i) res += d[t];

        for(int j = 1;j <= n;j++) {
            d[j] = min(d[j],g[t][j]);
        }

        st[t] = 1;
    }

    return res;
}

heap + Prim算法代码非常多，不推荐写

Kruskal

时间复杂度为O(mlogm)

Step

1. 将所有边按照权重进行排序
2. 枚举每条边a，b，权重为c，如果a，b不连通，将这条边加入到集合中

如何将两个点连通可以参考一下并查集，p[a] = b

Kruskal代码

int kruskal() {
    sort(edges,edges + m,cmp);
    for(int i = 1;i <= n;i++) p[i] = i;

    int res = 0,cnt = 0;
    for(int i = 0;i < m;i++) {
        int a = edges[i].a,b = edges[i].b,c = edges[i].c;
        
        a = find(a),b = find(b);
        if(a != b) {
            p[a] = b;
            res += c;
            cnt++;
        }
    }
    //如果发现边数不足n - 1说明无法构建最小生成树
    if(cnt < n - 1) return INF;
    return res;    
}