基础图论算法--最小生成树——prim、Kruskal算法

生成树的概念：是包含连通图中所有的顶点，并且只含尽可能少的边
特点一：若砍去他的一条边，则会使生成树变成非连通图
特点二：若给他增加一条边，则会形成图中的一条回路

Prim（普利姆）算法

从某一个顶点开始构建生成树，每次将代价最小的新顶点纳入生成树，直到所有的顶点都纳入为止
注意：Prim算法看的是顶点；采用的是贪心的策略
Prim算法更使适应稠密图，时间复杂度为：O(n^2)，和Dijkstra算法很相似也肯可以用堆优化来解决稀疏图；但是对于稀疏图，我们更喜欢使用Kruskal（克鲁斯卡尔）算法，时间复杂度为：O(mlogm)

prime算法步骤

1. 初始化，把所有点到生成树的距离都初始化为正无穷
2. 找到集合外并且距离生成树最近的那个点
3. 把上个步骤的点加到集合中，用这个点再更新集合外的点的距离

例题：

#include 
#include 
#include 

using namespace std;

const int N = 510, INF = 0x3f3f3f3f;

int n, m;
int g[N][N];//稠密图我们使用邻接矩阵来存储点
int dist[N];//表示各个顶点到生成树的距离
bool st[N];//表示该节点是否加入到生成树中

int prim()
{
    memset(dist, 0x3f, sizeof dist);//初始化dist
    
    int res = 0;//最终结果
    for(int i = 0; i < n; i++)//每次循环选择一个点加入到生成树中,共有n个点
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;//如果没有在生成树中并且树的权重最小，则选择此点加入生成树中
        }
        
        if(i && dist[t] == INF) return INF;//如果最小点都这样，直接return
        if(i) res += dist[t];
        st[t] = true;
        
        for(int j = 1; j <= n; j++)//更新生成树外的点到生成树的距离
            dist[j] = min(dist[j], g[t][j]);
    }
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);//初始化邻接矩阵
    
    while(m--)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        g[a][b] = g[b][a] = min(g[a][b], c);//存储最小的权重即可
    }
    
    int t = prim();
    if(t == INF) puts("impossible");
    else printf("%d\n", t);
    
    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

Kruskal（克鲁斯卡尔）算法

Kruskal算法每次选择权值最小的边，使这条边的两头连通，知道所有的节点都连通
Kurskal算法是通过找边来构造最小生成树的；
Kruskal算法存边的方法任意，就用最简单的结构体存边即可
Kruskal算法需要判断两个点是否在集合中，以及如何把这两个点连城的一条边加入到集合中，这就需要我们使用并查集的知识了

Kruskal算法步骤

1. 将所有边按权重从小到大排序 O(mlongm)
2. 枚举每条边a到b的权重为c，如果a和b不连通，则将这条边加入到生成树种；注意：刚开始每个点都是不连通的

#include 
#include 
#include 

using namespace std;

const int N = 100010, M = 200010, INF = 0x3f3f3f3f;

int n, m;
int p[N];//并查集

struct Edge
{
    int a, b, c;
    
    bool operator< (const Edge &C)const//重载<运算符
    {
        return c < C.c;
    }
}edges[M];

int find(int x)//并查集
{
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int Kruskal()
{
    sort(edges, edges + m);//将所有边进行排序
    
    for(int i = 1; i <= n; i++) p[i] = i;//初始化并查集
    
    int res = 0, cnt = 0;//res就是最终的答案，最小生成树的边权之和，cnt记录的是加入到树的集合中边的数量
    for(int i = 0; i < m; i++)//循环m条边
    {
        int a = edges[i].a, b = edges[i].b, c = edges[i].c;
        a = find(a), b = find(b);
        if(a != b)//说明a和b不在一个集合中
        {
            p[a] = b;//把a和b加到一个集合中
            res += c;
            cnt++;
        }
    }
    if(cnt < n - 1) return INF;//不可以生成最小生成树
    else return res;
}

int main()
{
    scanf("%d%d", &n, &m);
    
    for(int i = 0; i < m; i++)
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        edges[i] = {a, b, c};
    }
    
    int t = Kruskal();
    
    if(t == INF) puts("impossible");
    else printf("%d\n", t);
    
    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