Kruskal算法

时间复杂度：

  • O(mlogm)

使用范围

  • 求朴素最小生成树
  • 求最小生成森林，(求最小生成树的前一半)
  • 已知一些边，求最小生成树(求最小生成树的后一半)

具体实现：

  • 将所有边按照权重从小到大排序
  • 枚举每条边的顶点a, b, 权重c，若a, b不在一个集合，则合并a, b集合, 反之则跳过，判断下一条边

算法证明：

  • 证明思路与prim算法类似。
    • 如何证明这条边一定可以被选？
    • 假设不选当前边，最终得到了一棵树。然后将这条边加上，那么必然会形成一个环，在这个环上，一定可以找出一条长度不小于当前边的边，那么把当前边替换上去，结果一定不会变差。
  • 证明结论：若该边的两点所在的集合不同，则该边必定在最小生成树中
  • 证明结论如下：
    • 反证法：假设没有选择该边x1，则必定选择了之后的边x2使得两集合合并，使之形成最小生成树
    • 证明：把边x1加到用x2形成的最小生成树中，则会在形成一个环，且该边一定包含x1,x2，此时若把x2去除，则形成的也为一个生成树，且因为x1小于x2，新生成的生成树比原来的权值和还小，则可证x1比x2更合适，所以得证，若上述证明结论的情况发生，则必定成立！

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
struct Edge
{
    int a, b, w;
    bool operator < (const Edge &W)const
    {
        return w < W.w;
    };
}edge[N];

int find(int x)
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// kruskal 算法同样可以求最小生成森林（不全部连通的最小生成树）
int kruskal()
{
    int res = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = find(edge[i].a), b = find(edge[i].b);
        if(a != b) p[a] = b;
        else res += edge[i].w;
    }
    
    return res;
}