[算法学习]Kruskal求最小生成树

树是一种无环图，形似树而得名

而有一类著名的问题便是在图中选取一些点和一些边组成一棵树

当边权和最小时称为：最小生成树

Kruskal算法是求出最小生成树的一种方法

前置知识：贪心思想，并查集

Kruskal算法的基本思路：

将所有边按边权从小到大排序，遍历每个边，判断边的两个结点是否已经被选取进入最小生成树中了

如果没有则放入其中，如果有则继续判断下一条边

正确性：因为经过边权排序，保证了使每个点进入最小生成树的边权都最小，使得最终结果最小。

代码：

int f[5005];
int getf(int u){
    if(f[u] == u) return u;
    return f[u] = getf(f[u]);
}

void merge(int u, int v){
    int t1 = getf(u), t2 = getf(v);
    if(t1 != t2){
        f[t1] = t2;
    }
}

bool judge(int u, int v){
    int t1 = getf(u), t2 = getf(v);
    if(t1 != t2)
        return false;
    return true;
}
//上面是并查集

int n,m;
int a,b,c;
long long ans;

const int maxn = 2e5 + 50;
struct edge{
    int u,v,w;
    bool operator<(const edge q){
        return this->w < q.w;
    }
}edges[maxn];
//直接存边

int main(){
    cin>>n>>m;
    for(int i = 1; i <= n; i++)
        f[i] = i;
//初始化并查集

    for(int i = 1; i <= m; i++){
        scanf("%d%d%d", &a, &b, &c);
        edges[i].u = a, edges[i].v = b, edges[i].w = c;
    }
    sort(edges + 1, edges + m + 1);
//读入边，排序

    for(int i = 1; i <= m; i++){
        if(!judge(edges[i].u, edges[i].v)){
            merge(edges[i].u, edges[i].v), ans += edges[i].w;
        }
    }
//Kruskal核心代码
    cout<<ans;
    return 0;
}

时间复杂度大概是O(mlogm) m为边数。