最小生成树问题（MST）- prim和kruscal算法

一、prim算法

参考链接：
https://blog.csdn.net/gettogetto/article/details/53216951

思想：

    Prim算法从任意一个顶点开始，每次选择一个与当前顶点集（MST点集）最近的一个顶点，并将两顶点之间的边加入到树中。稍微困难一点的地方在于当前点集到 每个点的距离dist[i]数组，需要不断地去更新维护。

代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAX (1<<31)-1
using namespace std;

int mp[1005][1005];
int dist[1005]; //记录MST中的点集 到所有点的最短距离。
int vis[1005]; //标记当前点是否在MST中

int main() {

    int n,m;
    int l,r,w;

    while(~scanf("%d%d",&n,&m)){

        //输入边
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                mp[i][j] = MAX;

        for(int i=0;i<m;i++){

            scanf("%d%d%d",&l,&r,&w);
            mp[r][l] = mp[l][r] = w;
        }

        //初始化MST, 第一个点加入MST;更新最短距离
        memset(vis,0, sizeof(vis));
        vis[1] = 1;
        for(int i=1;i<=n;i++)
            dist[i] = mp[1][i];

        //遍历n-1次找最近点的程序
        int T=n-1;
        int ok=1;
        int sumVal = 0;
        while(T--) {
            int index = 0;
            int minor = MAX;
            //找距离MST点集最近的点
            for (int i = 1; i <= n; i++)
                if (!vis[i] && dist[i] < minor) {
                    minor = dist[i];
                    index = i;
                }

            //index加入MST中
            if (!index) {
                ok = 0;
                break;
            }
            else {
                vis[index] = 1;
                sumVal += minor;
            }
            //更新 到每个点的最短距离
            for (int i = 1; i <= n; i++)
                if (!vis[i] && mp[index][i] < dist[i])
                    dist[i] = mp[index][i];
        }


        if(ok)
            printf("%d\n",sumVal);
        else
            puts("-1");
    }



    return 0;
}

二、kruscal算法

思想：
不断合并两个不同的连通子图，最后成为一个连通图。具体地是 给所有边按照升序排列，然后从头遍历每一条边，如果这个边的两个顶点属于不同连通图，合并两个连通图；如果是同一个连通图，不操作（这里合并会形成环）。
难点在于“查询两个顶点是否属于不同连通图”和“合并两个连通图”可以用 并查集来实现。

代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

struct Edge{
    int l,r,w;
}E[50005];

int fa[10005];


bool cmp(Edge a, Edge b){

    return a.w<b.w;
}

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

    return fa[x] = find(fa[x]);
}

int main() {

    int n,m;
    int a,b,w;

    while(~scanf("%d%d",&n,&m)){

        for(int i=1;i<=n;i++)
            fa[i] = i;

        for(int i=0;i<m;i++){

            scanf("%d%d%d",&a,&b,&w);
            E[i].l = a;
            E[i].r = b;
            E[i].w = w;
        }

        //根据边权值排序，升序
        sort(E,E+m,cmp);

        int cnt = 0; //加入生成树中的边个数
        int sumVal = 0; //边的权值和
        for(int i=0;i<m;i++){

            int x= find(E[i].l);
            int y = find(E[i].r);

            if(x!=y){
                fa[x] = y;
                cnt++;
                sumVal+= E[i].w;
            }
        }

        if(cnt==n-1)
            printf("%d\n",sumVal);
        else
            puts("-1");


    }




    return 0;
}

三、二者比较

n为顶点个数，m为边的个数。

1. prim算法需要构造一个n*n的邻接矩阵，故n不能太大。因此prim算法适合n较小(n<=1000)，边较多的稠密图。
2. kruscal算法不用管点的数量，只要边的数量<=10^6级别就行，所以kruscal的适用范围更广，而且代码实现更为简单，推荐~