Kruskal 算法学习笔记

Vct14 · 2023-07-04 21:52:31 · 算法·理论

1 前言

本文主要讲解 Kruskal 算法入门。

2 算法简介

2.1 最小生成树

最小生成树（最小代价生成树）是指一个有 n 个结点的连通图的有着所有 n 个点、最少边和最小代价的子图。

2.2 Kruskal 算法

Kruskal 算法（克鲁斯卡尔算法）是一种用来查找最小生成树的贪心算法，适用于稀疏图。核心知识点为并查集。

设边数为 E，则它的时间复杂度为 O(E log E)。

3 并查集

并查集是一系列不相交的集合，主要有两种操作：合并和查找。

简单来说，一开始，每个元素都为一个单独的集合，是这个集合的“老大”。

所以一个元素所在集合的最终老大就是它老大的老大的老大······可以通过递归来找到。在递归时，可以进行压缩路径：直接将老大的老大的老大······设为自己的老大。

• 查询：查询两个元素是否在同一个集合中。

我们可以判断两个元素所在的集合的最终老大是否是同一个人。

• 合并：把两个元素所在的集合合并为一个集合。

我们可以将集合 b 的最终老大的老大改为集合 a 的最终老大。

给出并查集的模板代码：

#include<bits/stdc++.h>
using namespace std;

int f[10002];//每个人的老大 

int find(int x){//递归找最终老大 
    if(f[x]==x) return x;
    else return f[x]=find(f[x]);//压缩路径
}

int main(){
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=n; i++) f[i]=i;//自己就是老大 
    while(m--){
        int z,x,y;
        cin>>z>>x>>y;
        if(z==1) if(find(x)!=find(y)) f[find(x)]=find(y);//合并 
        if(z==2){//查询 
            if(find(x)==find(y)) cout<<"Y\n";
            else cout<<"N\n";
        }
    }
    return 0;
}

推荐一篇博客，可自行观看。

4 算法实现

例题：P3366 【模板】最小生成树

给出一个 n 个点、m 条边的无向图，求出最小生成树的各边的长度之和。如果该图不连通，则输出 orz。

4.1 怎样存边

我们可以使用一个结构体，存下一条边连接的两个点及距离。

4.2 怎样判断是否连通

这里需要运用并查集，最开始时，每一个点都为一个连通分量。若节点 u 和节点 v 间有一条边，则把节点 u 所在的集合与节点 v 所在的集合合并。

最终只剩下 1 个连通分量时，则此图连通。

当然，因为使一个 n 个点的图连通的最少边数（最小生成树边数）为 n-1（如图 1-1），所以也可以在已经取了 n-1 条边时结束。

4.3 怎样选边

既然有 m 条边，但我们只需要选择 n-1 条边，那么如何选择呢？

因为每条边有不同的长度，而题目要求求最短的长度，所以我们可以将所有边按长度从小到大排序。

然后，我们可以依次遍历每一条边：

若这两个点不在同一个集合内（不连通），则可以选择这一条边。我们让总长度加上这一条边的距离，边的数量加 1，再将两个点所在的集合合并。

当有边数 p=n-1 时，我们可以直接输出距离，并使用 return 0 结束程序。若没有 return 0，则可以直接输出 orz。

给一组数据帮助理解：Link。

由此可以建出图 1-2。（右边为排序后的结果）

4.4 完整代码

#include<bits/stdc++.h>
using namespace std;

int fa[5002];//祖先，用于并查集

struct Edge{
    int x,y,S;
}e[200002];

int find(int x){//并查集找祖先
    if(fa[x]==x) return x;
    return fa[x]=find(fa[x]);
}

void add(int m,int x,int y,int z){//建边
    e[m].x=x;
    e[m].y=y;
    e[m].S=z;
}

bool cmp(Edge a,Edge b){
    return a.S<b.S;
}

int main(){
    int n,m;
    cin>>n>>m;
    int x,y,z;
    for(int i=1; i<=n; i++) fa[i]=i;
    for(int i=1; i<=m; i++){
        cin>>x>>y>>z;
        add(i,x,y,z);
    }
    sort(e+1,e+m+1,cmp);
    int sum=0,p=0;
    for(int i=1; i<=m; i++){
        int x=e[i].x,y=e[i].y;
        if(find(x)!=find(y)){//不在同一集合内
            sum+=e[i].S;
            p++;
            fa[find(x)]=y;//合并
        }
        if(p==n-1){//选完了
            cout<<sum;
            return 0;
        }
    }
    cout<<"orz";
    return 0;
}

5 习题

• P1546 [USACO3.1] 最短网络 Agri-Net

模板题 2.0，输入一个矩阵代表两点间的距离，保证连通。

• P2820 局域网

• P2330 [SCOI2005] 繁忙的都市

• P2872 [USACO07DEC] Building Roads S

• P2212 [USACO14MAR] Watering the Fields S

• P1991 无线通讯网

[$ \rule{45pt}{15pt}\kern{-38pt}\color{white} \raisebox{4.7pt}{\footnotesize\sf 习题题单}

\rule{45pt}{15pt}\kern{-38pt}\color{white} \raisebox{4.7pt}{\footnotesize\sf 习题解析}