本文主要介绍了图论中最小生成树问题的 2 种算法：Prim 和 Kruskal

Prim（加点法）

基本信息

每次迭代选择边权最小的边对应的点，加入到最小生成树中。
算法从某个顶点 startstart 开始，逐渐延伸覆盖整个连通网的所有顶点
pic-solution

时间复杂度：O(n2)O(n^2)

算法思想

蓝白点思想：白点表示已经进入最小生成树的点，蓝点表示没有进入最小生成树的点。
每次循环都将一个蓝点 uu 变为白点，并且这个蓝点 uu 与白点相连的最小边权 min(weight[u]) 还是当前所有蓝点中最小的。
这样相当于向生成树中添加了 n−1n-1 次最小的边，最后得到的一定是最小生成树

算法描述

以 11 为起点生成最小生成树，min[v] 表示蓝点 v 与白点相连的最小边权，mst 表示最小生成树的权值之和

  1. 初始化：min[v]=INF(v≠1)(v\ne 1)   min[1]=0   mst=0
1
2
3
4
5
6
7
8
9
for(int i=1;i<=n;i++)
{
    1. 寻找 min[u] 最小的蓝点 u
    2. 将 u 标记为白点
    3. mst+=min[u];
    4. for(与白点 u 相连的所有蓝点 v)
        if(weight[u][v]<min[v])
            min[v]=weight[u][v];
}
  1. 算法结束，mst 即为最小生成树的权值之和

例题 - YBT 1349

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
#include<bits/stdc++.h>
using namespace std;
const int LEN=105,INF=0x3f;
int graph[LEN][LEN];
int minn[LEN];
bool vis[LEN];
int n,mst=0;
void init()
{
    memset(minn,INF,sizeof(minn));
    minn[1]=0;
    memset(vis,true,sizeof(vis));
}
int main()
{
    cin>>n;
    init();
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>graph[i][j];
    for(int i=1;i<=n;i++)
    {
        int k=0;
        for(int j=1;j<=n;j++)
            if(vis[j]&&(minn[j]<minn[k]))
                k=j;
        vis[k]=false;
        for(int j=1;j<=n;j++)
            if(vis[j]&&(graph[k][j]<minn[j]))
                minn[j]=graph[k][j];
    }
    for(int i=1;i<=n;i++)  mst+=minn[i];
    cout<<mst;
    return 0;
}

Kruskal

基本信息

  • Kruskal 算法是一种巧妙利用并查集来求最小生成树的算法。
  • Kruskal 算法将一个连通块当做一个集合。

时间复杂度为 O(E log(E))O(E\ log(E))，E为边数。

算法思想

  1. 首先将所有的边按从小到大顺序排序（一般使用快排），并认为每一个顶点都是孤立的，分属于 nn 个独立的集合。
  2. 然后按顺序枚举每一条边，如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。
  3. 直到选取了 n−1n-1 条边为止。

通过上面的模拟能够看到，Kruskal 算法每次都选择一条最小的，且能合并两个不同集合的
边，一张 nn 个顶点的图总共选取 n−1n-1 次边。因为每次我们选的都是最小的边，所以最后的生成树一定是最小生成树。每次我们选的边都能够合并两个集合，最后 nn 个顶点一定会合并成一个集合。通过这样的贪心策略，Kruskal 算法就能得到一棵有 n−1n-1 条边，连接着 nn 个顶点的最小生成树。

算法描述

  1. 初始化并查集：fa[x]=x，初始化总权值和：mst=0
  2. 将所有边用快排 从小到大 排序
  3. 计数器 k=0
1
2
3
4
5
6
7
8
9
10
for(int i=1;i<=m;i++)
{
    if(这是一条 u,v 不属于同一集合的边 u->v)
    {
        1. 合并 u,v 所在的集合，相当于把 u->v 加入最小生成树
        2. mst+=weight[u][v]
        3. k++;
        4. if(k==n-1)  break; 最小生成树已经生成，跳出循环
    }
}
  1. 算法结束，mst 即为最小生成树的总权值之和

例题 - Luogu 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
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int LEN=2e5+5;
struct Edge
{
    int u,v,w;
}edge[LEN];
int cnt;
int fa[5005];
int n,m,mst=0,edges_cnt=0;
int find(int x)
{
    if(fa[x]!=x)  fa[x]=find(fa[x]);
    return fa[x];
}
void merge(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)  fa[fx]=fy;
    return;
}
void addedge(int u,int v,int w)
{
    cnt+=1;
    edge[cnt].u=u;
    edge[cnt].v=v;
    edge[cnt].w=w;
    return;
}
bool cmp(Edge a,Edge b){return a.w<b.w;}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        addedge(u,v,w);
    }
    for(int i=1;i<=n;i++)  fa[i]=i;
    stable_sort(edge+1,edge+cnt+1,cmp);
    for(int i=1;i<=cnt;i++)
    {
        if(find(edge[i].u)!=find(edge[i].v))
        {
            merge(edge[i].u,edge[i].v);
            mst+=edge[i].w;
            edges_cnt++;
        }
        if(edges_cnt==m)  break;
    }
    if(edges_cnt<n-1)  cout<<"orz";
    else  cout<<mst;
    return 0;
}
许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

快来参与讨论吧~