Skip to content

最小生成树

理论

最小生成树的定义见生成树。 常见的两种相关算法分别是加点的Prim算法和加边的Kruskal算法。

Prim算法

prim算法适用于稠密图，通过选择最近点增加以构建树，总体思路是循环选择距离当前树最近且不在树中的点加入树，依赖邻接矩阵实现。 在数据规模较大的情况下，考虑使用优先队列和堆优化空间。

实现

朴素Prim的思路如下：

  1. 初始化和建图。需要至少一个存边的二维数组edges，以及一个存当前未加入生成树的点与生成树的最小距离的一维数组lowcost，元素均初始化为一个极大值INF。 选择或确定生成树的第一个元素，将lowcost中对应的元素置为0，将其它所有元素置为和第一个元素之间的直接连边的边权。如果没有直接连边，则默认为INF。
  2. 循环，选择距离生成树最小距离的点加入生成树，直到所有点都加入生成树。
  3. 遍历lowcost，找到最小权的边和对应的节点
  4. 将节点加入生成树，累加总边权
  5. 遍历lowcost，检查未加入生成树的节点和本轮加入生成树的节点的直接连边边权，如果比lowcost中记录的更小就更新。
  6. 返回总边权。
点击展开代码 
#include<iostream>
using namespace std;

const int MAX=1005;
const int INF=2147483647;

int n,m;    //顶点数、边数
int map[MAX][MAX];
int a,b,w;
int lowcost[MAX];
int sum=0;

int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++)map[i][j]=INF;
    }
    for(int i=0;i<m;i++){
        cin>>a>>b>>w;
        map[a][b]=w;
        map[b][a]=w;
    }

    //初始化lowcost
    for(int i=1;i<=n;i++){
        if(i==1)lowcost[i]=0;
        else lowcost[i]=map[1][i];
    }

    //prim
    for(int i=1;i<n;i++){
        int minP=-1;
        int minCost=INF;
        for(int j=1;j<=n;j++){
            if(lowcost[j]==0)continue;
            if(lowcost[j]<minCost){
                minCost=lowcost[j];
                minP=j;
            }
        }
        //更新lowcost
        sum+=lowcost[minP];
        lowcost[minP]=0;

        for(int j=1;j<=n;j++){
            if(lowcost[j]==0)continue;
            if(lowcost[j]>map[minP][j])lowcost[j]=map[minP][j];
        }
    }

    cout<<sum;


    return 0;
}

堆优化

Kruskal算法

kruskal算法适用于稀疏图，通过选择最短边构建树，总体思路是先对边权进行排序，然后从边权小的开始取，直到取到点数-1条边。 并非所有边都能取，只有一条边连接的两个点之间不连通时，这条边才能连接。因此，kryakal算法使用并查集辅助判断两点是否在同一连通图。

实现

总体思路如下：

  1. 初始化。结构体数组存边并按边权排序，初始化并查集
  2. 遍历边数组
  3. 根据并查集判断当前当前边能否加入生成树
  4. 更新并查集，累加边权
  5. 返回总边权