最小生成树

一个有nn个顶点的图，边个数一定大于等于n−1n-1。图的最小生成树指的是在这些边中选择n−1n-1条边，形成一棵包含所有顶点的树，这n−1n-1条边的权值之和在所有方案中最小。

Prim算法

基本描述

PrimPrim算法从点出发，每次选择与已加入节点距离最小的节点。时间复杂度为O(n2+m)O(n^2+m)一般在稠密图中使用。

代码实现

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
68
69
70
71
72
73
74
75
76
#include <bits/stdc++.h>
using namespace std;
#define Max 200000010
int graph[5050][5050];
long long Prim(int n)
{
    int vis[5050] = {0};
    long long ans = 0;
    vis[1] = 1;

    int dis[5010];//点到树集合距离
    for (int i = 1; i <= n; i++)
    {
        dis[i] = graph[1][i];
    }
    dis[1] = 0;
    int prePoint[5010];

    for (int i = 2; i <= n; i++)
    {
        int minDis = Max;
        int minP = -1;
        for (int j = 2; j <= n; j++)
        {
            if (vis[j] == 0 && dis[j] < minDis)
            {
                minDis = dis[j];
                minP = j;
            }
        }
        if (minP == -1) // 不连通
        {
            return -1;
        }
        ans += minDis;
        vis[minP] = 1;
        dis[minP] = 0;

        for (int j = 2; j <= n; j++)//更新与树中新添加点(minP)有关联的点，到树距离
        {
            if (!vis[j] && dis[j] > graph[minP][j])
            {
                dis[j] = graph[minP][j];
                prePoint[j] = minP;
            }
        }
    }
    return ans;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i <= n; i++)
    {
        for (int j = 0; j <= n; j++)
        {
            graph[i][j] = Max;
        }
    }
    for (int i = 0; i < m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u][v] = min(w, graph[u][v]);
        graph[v][u] = min(w, graph[v][u]);
    }
    long long ans = Prim(n);
    if (ans == -1)
    {
        cout << "orz" << endl;
    }
    else
        cout << ans << endl;
    return 0;
}

Kruskal算法

基本描述

KruskalKruskal算法从边出发，首先将边按照权值从小到大排序，将每个点当作一个孤立的集合，遍历边如果此边连接着两个孤立的集合，那么把这条边加入最小生成树，如果此边属于一个连通子集则跳过，直至选出n−1n-1条边。如果最终没有n−1n-1条边则不存在生成树。

代码示例

并查集来判断两点是否连通。

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
68
69
70
71
72
73
74
75
76
77
78
79
#include <bits/stdc++.h>
using namespace std;
#define ll long long
struct edge
{
    int u;
    int v;
    ll w;
} e[5050];
bool cmp(edge a, edge b)
{
    return a.w < b.w;
}
// 并查集
vector<int> pre(2020);
vector<int> Rank(2020);
void UnionFind(int n)
{
    for (int i = 0; i <= n; i++)
    {
        pre[i] = i;
        Rank[i] = 0;
    }
}
int Find(int x)
{
    while (x != pre[x])
        x = pre[x];
    return x;
}
void join(int x, int y)
{
    int root_x = Find(x);
    int root_y = Find(y);
    if (Rank[root_x] == Rank[root_y])
    {
        Rank[root_x]++;
        pre[root_y] = root_x;
    }
    else if (Rank[root_x] > Rank[root_y])
        pre[root_y] = root_x;
    else
        pre[root_x] = root_y;
}

ll Kruskal(int n, int m)
{
    sort(e, e + m, cmp); // 权值从小到大
    UnionFind(n);
    int num = 0;
    ll ans = 0;
    for (int i = 0; i < m; i++)
    {
        int u = e[i].u;
        int v = e[i].v;
        int w = e[i].w;
        if (Find(u) != Find(v))
        {
            num++;
            ans += w;
            join(u, v);
            if (num == n - 1)
                break;
        }
    }
    return ans;
}
int main()
{
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> e[i].u >> e[i].v >> e[i].w;
    }
    cout << Kruskal(n, m) << endl;

    return 0;
}