最小生成树算法

最小生成树算法

从具有n个节点的连通图中选择 n-1 条边，使得所组成的树的权值最小，即为最小生成树

即以最小的成本（边的权值）将图中所有节点链接到一起

Prim

prim算法 是从节点的角度 采用贪心的策略 每次寻找距离 最小生成树最近的节点 并加入到最小生成树中

选节点 -> 加入 -> 更新其他点距离

  1. 循环n次，找到集合（最小生成树中的节点所组成）外距离最近集合最近的点t
  2. 点t加入集合
  3. 用 t 更新集合外其他点到集合的距离（到集合中任意一点的最小距离）
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
#include <bits/stdc++.h>

using namespace std;

const int N = 510;
const int M = 1e5+10;

int h[N],e[M],ne[M],idx,w[M];
int n,m;
int d[N],st[N];
long long res;

void add(int u,int v,int value){
    e[idx] = v; w[idx] = value; ne[idx] = h[u]; h[u] = idx++;
}

void dfs(int u){
    for(int i=h[u];i!=-1;i=ne[i]){
        int j = e[i];
        if(!st[j] && w[i] < d[j]){
            d[j] = w[i];
        }
    }
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof(h));
    for(int i=0;i<m;i++){
        int u,v,w;
        cin >> u >> v >> w;
        add(u,v,w); add(v,u,w);
    }
    memset(d,0x3f,sizeof(d));
    memset(st,0,sizeof(st));
    
    int cur = 1;    //初始节点设置为1
    d[1] = 0;
    // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
    for(int i=1;i<n;i++){
        
        int minv = 1e9; //每次选新节点前都要重新赋值
        
        //1. 选节点
        for(int j=1;j<=n;j++){
            if(!st[j] && d[j] < minv){
                minv = d[j];
                cur = j;
            }
        }
        
        //2.加入最小生成树
        st[cur] = 1;

        //3. 更新距离
        dfs(cur);
    }
    //d[1] 不用计算进来
    for(int i=2;i<=n;i++){
        if(d[i] > 10000){ //图中涉及边的边权的绝对值均不超过 10000
            cout << "impossible";
            return 0;
        }
        res += d[i];
    }
    cout << res;
    return 0;
}

堆优化版Prim

  1. 使用小根堆来判断 d数组 里的最小值
  2. 记录被确认的点的数量，当队列为空后，判断点数量是否与总节点数相同来判断是否有最小生成树
  3. 无向图的初始化：边数的两倍（const int M = 2e5+10）; add(a,b,w); add(b,a,w);

tips:

  1. M 数组来开小了，会超时
  2. if(st[cur]) continue; 必不可少的剪枝，防止超时 (不加会一直循环下去，如果非堆优化版本可以不加，因为它是通过n-1次的for循环来控制的)
  3. const int M = 3e5+10; //边数不够的话，也会报TLE , 无向图要开两倍（越大越好）
    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
    80
    #include <bits/stdc++.h>

    using namespace std;

    typedef pair<int,int> PII;

    const int N = 510;
    const int M = 2e5+10;

    int h[N],e[M],ne[M],idx,w[M];
    int n,m;
    int d[N],st[N];
    long long res;

    priority_queue<PII,vector<PII>,greater<PII>> q;

    void add(int u,int v,int value){
        e[idx] = v; w[idx] = value; ne[idx] = h[u]; h[u] = idx++;
    }

    void dfs(int u){
        for(int i=h[u];i!=-1;i=ne[i]){
            int j = e[i];
            if(!st[j] && w[i] < d[j]){
                d[j] = w[i];
                q.push({d[j],j});
            }
        }
    }

    int main(){
        cin >> n >> m;
        memset(h,-1,sizeof(h));
        for(int i=0;i<m;i++){
            int u,v,w;
            cin >> u >> v >> w;
            add(u,v,w); add(v,u,w);
        }
        memset(d,0x3f,sizeof(d));
        memset(st,0,sizeof(st));
        
        int cur = 1;    //初始节点设置为1
        d[1] = 0;
        q.push({0,1});
        // 我们只需要循环 n-1次，建立 n - 1条边，就可以把n个节点的图连在一起
        while(q.size()){
            
            int minv = 1e9; //每次选新节点前都要重新赋值
            
            //1. 选节点
            for(int j=1;j<=n;j++){
                if(!st[j] && d[j] < minv){
                    minv = d[j];
                    cur = j;
                }
            }
            
            //1.选节点
            PII t = q.top();
            cur = t.second;
            q.pop();
            
            if(st[cur]) continue; //必不可少的剪枝，防止超时
            //2.加入最小生成树
            st[cur] = 1;

            //3. 更新距离
            dfs(cur);
        }
        //d[1] 不用计算进来
        for(int i=2;i<=n;i++){
            if(d[i] > 10000){ //图中涉及边的边权的绝对值均不超过 10000
                cout << "impossible";
                return 0;
            }
            res += d[i];
        }
        cout << res;
        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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>

using namespace std;

typedef pair<int,int> PII;
const int N = 510;
const int M = 2e5+10; //无向图，边数的两倍
const int INF = 0x3f3f3f3f;

int h[N],e[M],ne[M],idx,w[M];
int d[N];
bool st[N];
int n,m;

void add(int a,int b,int v){
    e[idx] = b; w[idx] = v;
    ne[idx] = h[a];
    h[a] = idx;
    idx++;
}

int prim(){
    priority_queue<PII,vector<PII>,greater<PII>> q;
    int res = 0,cnt = 0; //定义在函数里的值一定要初始化，否则不会给它设置为 0 
    memset(d,0x3f,sizeof(d));
    d[1] = 0;
    q.push({0,1}); //距离，节点编号
    while(q.size()){
        //不属于集合 && 距离集合最小的点
        /*朴素版
        int t = -1;
        for(int i=1;i<=n;i++){
            if(!st[i] && (t == -1 || d[i] < d[t])){
                t = i;
            }
        }
        */
        //堆优化版本
        auto t = q.top();
        int ver = t.second;
        q.pop();
        
        if(st[ver]) continue;
        //把点t加到集合当中去，更新权值
        st[ver] = true;
        cnt++; //不存在生成树即cnt != n
        
        // res += q.top().first; //前面已经pop 了因此不能这样写
        res += t.first;
        
        //更新其他点到 集合 的距离
        for(int i=h[ver];i!=-1;i=ne[i]){
            int j = e[i];
            if(st[j]) continue; 
            if(w[i] < d[j]){
                d[j] = w[i];
                q.push({d[j],j}); //只有在确定最小值会被更新时，再push入队
            }
        }
    }
    if(cnt != n) return INF; 
    return res;
}

int main(){
    cin >> n >> m;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=m;i++){
        int a,b,w;
        cin >> a >> b >> w;
        add(a,b,w); add(b,a,w); //无向图
    }
    int ans = prim();
    if(ans == INF) cout << "impossible";
    else{
        cout << ans;
    }
    return 0;
}

Kruskal

kruscal的思路：

排序边 + 并查集

  • 边的权值排序，因为要优先选最小的边加入到生成树里

  • 遍历排序后的边

    • 如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
    • 如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合
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
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Edge {
    int l, r, val;
};


int n = 10001;

vector<int> father(n, -1); 

void init() {
    for (int i = 0; i < n; ++i) {
        father[i] = i;
    }
}

int find(int u) {
    return u == father[u] ? u : father[u] = find(father[u]); 
}

void join(int u, int v) {
    u = find(u); 
    v = find(v); 
    if (u == v) return ; 
    father[v] = u;
}

int main() {

    int v, e;
    int v1, v2, val;
    vector<Edge> edges;
    int result_val = 0;
    cin >> v >> e;
    while (e--) {
        cin >> v1 >> v2 >> val;
        edges.push_back({v1, v2, val});
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
            return a.val < b.val;
    });

    vector<Edge> result; // 存储最小生成树的边

    init();

    for (Edge edge : edges) {

        int x = find(edge.l);
        int y = find(edge.r);


        if (x != y) {
            result.push_back(edge); // 保存最小生成树的边
            result_val += edge.val; 
            join(x, y);
        }
    }

    // 打印最小生成树的边
    for (Edge edge : result) {
        cout << edge.l << " - " << edge.r << " : " << edge.val << endl;
    }

    return 0;
}
最小生成树算法
https://cs-lb.github.io/2024/05/21/搜索与图论/最小生成树算法/
作者
Liu Bo
发布于
2024年5月21日
许可协议