ฅ(๑˙o˙๑)ฅ 大家好, 欢迎大家光临我的博客：面向阿尼亚学习
算法学习笔记系列持续更新中~

---

---

一、前言

最小生成树定义：

一个有 n 个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有 n 个结点，并且有保持图连通的最少的边。最小生成树可以用kruskal（克鲁斯卡尔）算法或prim（普里姆）算法求出。

最小生成树其实是最小权重生成树的简称

---

二、Kruskal算法求最小生成树

时间复杂度 O(mlogm) ——m为边数，适合于求边稀疏的网的最小生成树

Kruskal算法是基于贪心的思想得到的。

Kruskal算法简述

首先我们把所有的边按照权值先从小到大排列，接着按照顺序选取每条边，如果这条边的两个端点不属于同一集合，那么就将它们合并，直到所有的点都属于同一个集合为止。

实现步骤

• 将所有边按照权值的大小进行升序排序，然后从小到大一一判断。

• 如果这个边与之前选择的所有边不会组成回路，就选择这条边分；反之，舍去。

• 直到具有 n 个顶点的连通网筛选出来 n-1 条边为止。

• 筛选出来的边和所有的顶点构成此连通网的最小生成树。

判断是否会产生回路的方法为：使用并查集。

在初始状态下给各各个顶点在不同的集合中。
遍历过程的每条边，判断这两个顶点的是否在一个集合中。
如果边上的这两个顶点在一个集合中，说明两个顶点已经连通，这条边不要。如果不在一个集合中，则要这条边。

int Kruskal()
{
    int res=0,cnt=0;//res记录最小生成树的树边权重之和,cnt记录的是全部加入到树的集合中边的数量(可能有多个集合)
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        if(find(a)!=find(b))
        //如果 a b 不在一个集合中
        {
            p[find(a)]=p[find(b)];//将a,b所在的两个集合连接起来
            cnt++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
            res+=w;//加入到集合中的边的权重之和
        }
    }

    if(cnt==n-1) return res;//树中有n个节点便有n-1条边，可以生成最小生成树
    else return 0x3f3f3f3f;//如果cnt不等于n-1的话,说明无法生成有n个节点的树
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

例题：

给定一个 n 个点 m 条边的无向图，图中可能存在重边和自环，边权可能为负数。
求最小生成树的树边权重之和，如果最小生成树不存在则输出 impossible。

输入样例：
4 5
1 2 1
1 3 2
1 4 3
2 3 2
3 4 4
输出样例：
6

#include<iostream>
#include<algorithm>
#include<cstring>

using namespace std;

const int N=200010,M=100010;         

int p[M];
int n,m;

struct Edge
{
    int a,b,w;
//重载小于号，因为在给边排序的时候是按照边的权重进行排序的，这样当两个边进行比较的时候就会使用它们的权重进行比较了
     bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[N];

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

int Kruskal()
{
    int res=0,cnt=0;//res记录最小生成树的树边权重之和,cnt记录的是全部加入到树的集合中边的数量(可能有多个集合)
    for(int i=0;i<m;i++)
    {
        int a=edges[i].a,b=edges[i].b,w=edges[i].w;
        if(find(a)!=find(b))
        {
            p[find(a)]=p[find(b)];//将a,b所在的两个集合连接起来
            cnt++;//因为加入的是a-b的这一条边,将a,b所在的两个集合连接之后,全部集合中的边数加1
            res+=w;//加入到集合中的边的权重之和
        }
    }

    if(cnt==n-1) return res;//可以生成最小生成树
    else return 0x3f3f3f3f;//树中有n个节点便有n-1条边,如果cnt不等于n-1的话,说明无法生成有n个节点的树
}

int main()
{
    cin>>n>>m;

    for(int i=0;i<n;i++) p[i]=i;//初始化并查集

    for(int i=0;i<m;i++)//读入每条边
    {
        int a,b,w;
        cin>>a>>b>>w;
        edges[i]={a,b,w};
    }

    sort(edges,edges+m);//将边的权重按照大小一一排序

    int t=Kruskal();

    if(t==0x3f3f3f3f) puts("impossible\n");
    else cout<<t<<endl;

    return 0;
}
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

---

最后

莫言真理无穷尽，寸进自有寸进欢