最小生成树

Prim算法

朴素Prim算法

  1. 初始化 数组为正无穷
  2. 枚举之后的每条边（枚举 次）
  3. 找到离集合最近的点
  4. 用 更新其他点到集合的距离
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
#include <iostream>
#include <cstring>
using namespace std;

const int N =  510, INF = 0x3f3f3f3f; 

int n, m;
int dist[N], g[N][N];
bool st[N];

int prim()
{
    memset(dist, 0x3f, sizeof(dist));
    dist[1] = 0;
    int res = 0;
    for(int i = 0; i < n; i ++ )  //  与朴素版dijkstra一样更新n-1次
    {
        int t = -1;
        for(int j = 1; j <= n; j ++ )
            if(!st[j] && (t == -1 || dist[j] < dist[t]))
                t = j;
        res += dist[t];  // 在这里更新结果
        st[t] = true;
        for(int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);  // 注意这里的更新方式和dijkstra不一样
    }
    return res;
}


int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof(g));
    while(m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);  //  存储无向边
    }
    int t = prim();
    if(t > INF / 2)  printf("impossible\n");   //  为了保险可以写成t > INF / 2
    else printf("%d\n", t);
    return 0;
}

堆优化版(不常用) 略

Kruskal 算法

开一个结构体来存储所有的边

  1. 将所有边按边权进行排序

  2. 枚举每条边 ，及其权重

    如果 , 不连通--并查集

    将这条边加入集合中

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
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5 + 10, M = 1e5 + 10, INF = 0x3f3f3f3f;

int n, m;
int p[N];  // 并查集中用到的祖宗节点数组
struct Edge
{
    int a, b, w;
    bool operator< (const Edge & x) const{   // 重载了小于号方便排序
   //重载小于号是记得用const加这个结构体的名称
        return w < x.w;
    }
}edge[M];

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

int kruskal()
{
    sort(edge + 1, edge + 1 + m);
    for(int i = 1; i <= n; i ++ )  p[i] = i;  // 初始化并查集!!!!
    static int res, cnt;
    for(int i = 1; i <= m; i ++ )
    {
        int a = edge[i].a, b = edge[i].b, w = edge[i].w;
        if(find(a) != find(b))  //  如果这两个点不在同一个集合那就把它们加入进来
        {
            p[find(a)] = find(b);
            res += w;
            cnt ++ ;
            if(cnt == n - 1) break;  // 加了这个优化能稍微快一点 
        }
    }
    if(cnt < n - 1)  return INF;
    else return res;
}

int main()
{
    cin >> n >> m;
    for(int i = 1; i <= m; i ++ )
    {
        cin >> edge[i].a >> edge[i].b >> edge[i].w;
    }
    int x = kruskal();
    if(x > INF / 2)  printf("impossible\n");
    else printf("%d", x);
    return 0;
}