Kruskal最小生成树及应用

生成树：

已知连通图G，图上有n个顶点。

生成树是指图G的一个极小（边最少）连通子图，生成树上有n个顶点，n-1条边，且任意两点之间都是联通的。

最小生成树：

已知带权连通图G，图中有n个顶点，每条边都有权值。

要从图中抽出一棵生成树，使得树上所有边权之和最小，这棵树就叫做最小生成树（Mininum Spanning Tree，MST）。

常见解法有Kruskal算法和Prim算法。

Kruskal算法：

定义带权无向图G的边集合为E，再定义最小生成树的边集合为T，初始集合T=空。

1.首先把图G看成一个有n棵树的森林，图上每个顶点对应一棵树；

2.然后把边集E的每条边，按照权值从小到大进行排序；

3.按边权从小到大的顺序遍历每条边e=(u,v)，我们记顶点u所在的树为T_u，顶点v所在的树为T_v，如果T_u和T_v不是同一棵树，则我们将边e加入集合T，并将两棵树Tu和Tv进行合并；否则不进行任何操作。

算法执行完毕后，如果集合T包含n-1条边，则T就代表最小生成树中的所有边。

第三步操作需要对集合进行合并操作，因此要用并查集来维护。

算法复杂度：若使用快排则复杂度为O(ElogE)，总时间复杂度为O(ElogE+Vα(V))，其中α(V)可近似被当作常数。

带详细解释の模板：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAX_N = 100000;  // 最大顶点数
const int MAX_M = 100000;  // 最大边数

struct edge {
    int u, v, w;
}e[MAX_M];

int fa[MAX_N], n, m;  // fa 数组记录了并查集中结点的父亲

bool cmp(edge a,edge b) {
    return a.w < b.w;
}

// 并查集相关代码
int ancestor(int x) {  // 在并查集森林中找到 x 的祖先，也是所在连通块的标识
    if(fa[x] == x) return fa[x];
    else return fa[x] = ancestor(fa[x]);
}
int same(int x, int y) {  // 判断两个点是否在一个连通块（集合）内
    return ancestor(x) == ancestor(y);
}
void merge(int x, int y) {  // 合并两个连通块（集合）
    int fax = ancestor(x), fay = ancestor(y);
    fa[fax] = fay;
}

int main() {
    scanf("%d%d", &n, &m);  // n 为点数，m 为边数
    for (int i = 1; i <= m; i++) {
        scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w);  // 用边集数组存放边，方便排序和调用
    }
    sort(e + 1, e + m + 1, cmp);  // 对边按边权进行升序排序
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
    int rst = n, ans = 0;  // rst 表示还剩多少个集合，ans 保存最小生成树上的总边权
    for (int i = 1; i <= m && rst > 1; i++) {
        int x = e[i].u, y = e[i].v;
        if (same(x, y)) {
            continue;  // same 函数是查询两个点是否在同一集合中
        } else {
            merge(x, y);  // merge 函数用来将两个点合并到同一集合中
            rst--;  // 每次将两个不同集合中的点合并，都将使 rst 值减 1
            ans += e[i].w;  // 这条边是最小生成树中的边，将答案加上边权
        }
    }
    printf("%d
", ans);
    return 0;
}

View Code

自用模板：

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+10;//最大顶点数
const int maxm=1e5+10;//最大边数
struct edge
{
    int u,v,w;
    /*
    bool operator <(const edge &a)const
    {
        return w<a.w;
    }
    */
} e[maxm];
int fa[maxn],n,m;
bool cmp(edge a,edge b)
{
    return a.w<b.w;
}
int get(int x)
{
    if(fa[x]==x)return fa[x];
    return fa[x]=get(fa[x]);
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    sort(e+1,e+1+m,cmp);
    for(int i=1;i<=n;i++)fa[i]=i;
    int rest=n,ans=0;
    for(int i=1;i<=m&&rest>1;i++)
    {
        int x=get(e[i].u),y=get(e[i].v);
        if(x!=y)
        {
            fa[x]=y;
            rest--;
            ans+=e[i].w;
        }
    }
    printf("%d
",ans);
    return 0;
}

最小生成树的应用：

例一：最大边权最小的生成树

给定一个无向连通图，求出它所有生成树中最大边权最小的一棵。

解法：可二分，枚举生成树的边权上界之后判定是否存在边权不超过限制的生成树。

正解为直接求最小生成树，因为最小生成树中的最大边一定是所有生成树中最小的（联系最小生成树的生成原理）。

例二：次小生成树

给定一个无向连通图，求出它的边权总和第二小的生成树。

解法：枚举最小生成树上的n条边，对于其中某条边，从图中删除它以后计算剩余图的最小生成树，一共n-1棵。从这n-1棵生成树中找出最小的一颗，就是整个图的次小生成树。

例三：边权极差最小生成树

给定一个无向连通图，求它所有生成树中，最大边权和最小边权之差最小的生成树。

解法：利用例题一中给出的性质，枚举生成树上的最小边权min_w，计算边权最小为min_w的最小生成树，用当前最小生成树的最大边减去最小边来更新最终答案。