最小生成树基础算法学习

定义

我们定义无向连通图的 最小生成树（Minimum Spanning Tree，MST）为边权和最小的生成树。

注意：只有连通图才有生成树，而对于非连通图，只存在生成森林。

Kruskal 算法

简介

基本思想是从小到大加入边，是个贪心算法。

将所有边的边权排序，从小到大加入生成树中，如果某次加入会生成环就舍弃此边，直到加入了 $n - 1$ 条边，形成树。时间复杂度为 $O(m \log 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


struct Node{
    int x,y,v;
    bool operator < (const Node &a){
        return v<a.v;
    }
}a[500001];

int n,m,fa[500001];

int find(int i){
    if(fa[i]==i)return i;
    return fa[i]=find(fa[i]);
}

int Kruskal(){
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(a+1,a+1+m);
    int cnt=n,ans=0;
    for(int i=1;i<=m;i++){
        int x=find(a[i].x),y=find(a[i].y);
        if(x!=y){
            fa[x]=y;
            ans+=a[i].v;
            cnt--;
        }
        if(cnt==1)break;
    }
    return cnt;
}

例题

洛谷 P3366

 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


#include <bits/stdc++.h>
using namespace std;

struct Node{
    int x,y,v;
    bool operator < (const Node &a){
        return v<a.v;
    }
}a[500001];

int n,m,fa[500001];

int findset(int i){
    if(fa[i]==i)return i;
    return fa[i]=findset(fa[i]);
}

void Kruskal(){
    for(int i=1;i<=n;i++)fa[i]=i;
    sort(a+1,a+1+m);
    int cnt=n,ans=0;
    for(int i=1;i<=m;i++){
        int x=findset(a[i].x),y=findset(a[i].y);
        if(x!=y){
            fa[x]=y;
            ans+=a[i].v;
            cnt--;
        }
        if(cnt==1)break;
    }
    if(cnt==1)
        cout<<ans<<endl;
    else cout<<"orz\n";
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++)cin>>a[i].x>>a[i].y>>a[i].v;
    Kruskal();
    return 0;
}

Prim 算法

简介

基本思想是从一个点开始，不断加点，而不是 Kruskal 的加边

具体做法就是在当前图可连点上选择距离最近的一个点，将这个点加入图，继续找最近的点，直到所有的点都找到

时间复杂度一般为 $O(n^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


struct Node{
    int y,v;
    Node(int _y,int _v){y=_y;v=_v;}
};

vector<Node>edge[5001];
int n,m,dist[5001];
bool b[5001];

void Prim(){
    memset(b,0,sizeof(b));
    memset(dist,127,sizeof(dist));
    dist[1]=0;
    int ans=0,tot=0;
    for(;;){
        int x=-1;
        for(int j=1;j<=n;j++){    
            if(!b[j]&&dist[j]<1<<30)
                if(x==-1||dist[j]<dist[x])x=j;
        }
        if(x==-1)break;
        b[x]=1;
        ++tot;
        ans+=dist[x];
        for(auto j:edge[x]){
            dist[j.y]=min(dist[j.y],j.v);
        }
    }
    if(tot==n)
        cout<<ans<<endl;
    else
    cout<<"-1\n";        
}

例题

洛谷 P3366

 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


#include <bits/stdc++.h>
using namespace std;

struct Node{
    int y,v;
    Node(int _y,int _v){y=_y;v=_v;}
};

vector<Node>edge[5001];
int n,m,dist[5001];
bool b[5001];

void Prim(){
    memset(b,0,sizeof(b));
    memset(dist,127,sizeof(dist));
    dist[1]=0;
    int ans=0,tot=0;
    for(;;){
        int x=-1;
        for(int j=1;j<=n;j++){    
            if(!b[j]&&dist[j]<1<<30)
                if(x==-1||dist[j]<dist[x])x=j;
        }
        if(x==-1)break;
        b[x]=1;
        ++tot;
        ans+=dist[x];
        for(auto j:edge[x]){
            dist[j.y]=min(dist[j.y],j.v);
        }
    }
    if(tot==n)
        cout<<ans<<endl;
    else
    cout<<"orz\n";        
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        edge[x].push_back(Node(y,z));
        edge[y].push_back(Node(x,z));
    }
    Prim();
    return 0;
}