#创作计划# 最小生成树

AAA逃离森林湖的蔡锡龙批发

2026-08-17 09:53:20

发布于：广东

1阅读

0回复

0点赞

前言

接下来几天都是图论和树。
@Eucatastrophe‌

正文

最小生成树的定义

生成子图和生成树

一个包含原图中所有点的子图是原图的生成子图。
生成树是连通无向图的一个生成子图，但是其同时要求是一棵树（即在图的边中选择 $n-1$ 条边构成的树）。
注意只有连通无向图拥有生成树，对于不连通的图只有生成森林。

一个连通无向图的最小生成树是其边权最小的生成树。

如何实现最小生成树

Kruskal 算法

我们观察最小生成树的定义，可以发现由于其边权最小的定义，其存在一个贪心思路，即按边权从小到大向生成树加入边。
Kruskal 算法正是利用了这个贪心思路。

此外，由于 Kruskal 算法必须对两个点所属的集合进行判断（避免重复加入边而形成环），所以其必须同时使用并查集。
关于并查集的思路，可以参考我的往期文章，我自认为还好。（？）

Kruskal 算法的代码如下（包含并查集）：

int n, m;
// 并查集模版，带路径压缩
int parent[100010];
void init(){
    for(int i = 1;i <= n;i++) parent[i] = i;
}
int find(int x){//返回节点 x 的根节点编号
    if(parent[x] == x) return x;//父节点编号等于自身的节点是根节点
    else{
        parent[x] = find(parent[x]);//不是根节点，向父节点查询，同时存储以压缩路径
        return parent[x];//返回查询答案
    }
}
void unite(int x,int y){//合并节点 x,y 所属的集合
    parent[find(x)]//x 的根的父节点
        =
    find(y);//y 的根
}
int edge_sum;
int edge_count;
// 最小生成树边的数量：
// 对于一张有 n 个节点的图，如果其“最小生成树”没有 n - 1 条边，
// 则这个图是错误的。
struct Edge {
    int u, v, w;
    bool operator < (const Edge & other) const {
        return w < other.w;
    }
};
vector<Edge> g;
void Kruskal() {
    sort(g.begin(), g.end()); // 按照边权排序
    for(auto i : g) {
        int u = i.u, v = i.v, w = i.w;
        if(find(u) != find(v)) { // 不在一个集合，可以加入
            unite(u, v);
            edge_sum += w;
            edge_count ++;
        }
    }
    if(edge_count != n - 1) { // 不是生成树
        cout << "orz";
    }
    else cout << edge_sum;
}