最小生成树prim和kruskal算法

一般对于最小生成树的题，都逃不掉prim和kruskual算法，这里简单讲一下两种算法吧

例题：P3366

1.Kruskual算法

又被称为克鲁斯卡尔算法，一般用于处理点多边少的的最小生成树

其原理是：

类似于贪心算法，通过利用并查集来维护这个图的连通性，先将边按照权的大小开始排序（升序），然后依次开始检查边的两个端点在未添加这条边时是否已经连通，若没有连通，则将此边添加到最小生成树的图中，否则则跳过这条边。

依次执行上述动作，直到检查了所有的端点，便可以得出一个最小生成树

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-07-13 17:32:18
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 * 加入秩和压缩优化
 */ 

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

struct node
{
    int u,v,w;
}lst[200005];

int parent[200005];
int ranks[200005];

bool cmp(node s1, node s2) {
    return s1.w < s2.w;
}

int find(int x) {
    return x == parent[x] ? x : (parent[x] = find(parent[x]));
}

void toUnion(int x1, int x2) {
    int p1 = find(x1);
    int p2 = find(x2);

    if (ranks[p1] > ranks[p2]) {
        parent[p1] = p2;
    } else {
        parent[p2] = p1;
        
        if (ranks[p1] == ranks[p2]) {
            ranks[p2]++;
        }
    }
}

int main() {
    int n,m;
    cin>>n>>m;
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", &lst[i].u, &lst[i].v, &lst[i].w);
    }
    sort(lst + 1,lst + m + 1,cmp);
    // 读入数据并将数据按照边的权进行排序
    
    for (int i = 1; i <= n; i++)
    {
        parent[i] = i;
        // 初始化
    }

    int sum = 0, tot = 0, flag =0;

    for (int i = 1; i <= m; i++)
    {
        int u = lst[i].u;
        int v = lst[i].v;
        int w = lst[i].w;

        if (find(u) != find(v)) {
            // 依次检查两点是否连通，若不连通则将其连通，并加入所需代价
            toUnion(u, v);
            sum += w;
            tot++;
        }
        
        if (tot == n - 1 ) {
            // 当执行此程序时，生成了正确的最小生成树
            flag = 1;
            break;
        }
    }
    if (flag == 1) {
        cout<<sum<<endl;
        // 输出总的权
    } else {
        cout<<-1<<endl;
        // 所给数据不能生成最小生成树
    }
    
    return 0;
}

2.Prim算法

该算法请看这篇图文 （日常偷懒划水 ）

我给一份代码吧

/*
 * @Author: Mr.Sen
 * @LastEditTime: 2020-07-14 22:37:35
 * @Website: https://grimoire.cn
 * @Mr.Sen All rights reserved
 */ 
#include <bits/stdc++.h>
using namespace std;

const int M = 5001, INF = 999999999;
int n, e;
int value[M][M];
int lowCost[M];

void prim(int s)
{
    int i, j, count = 0, minn, k;
    for (i = 1; i <= n; i++)
        lowCost[i] = value[s][i];
    lowCost[s] = 0;
    for (i = 1; i < n; i++)
    {
        minn = INF;
        for (j = 1; j <= n; j++)
        {
            if (lowCost[j] && lowCost[j] < minn)
            {
                minn = lowCost[j];
                k = j;
            }
        }
        lowCost[k] = 0;
        count += minn;
        for (j = 1; j <= n; j++)
        {
            if (value[k][j] < lowCost[j])
                lowCost[j] = value[k][j];
        }
    }
    printf("%d\n", count);
}

int main()
{
    int x, y, weight;
    for (int i = 0; i <= M; i++)
        for (int j = 0; j <= M; j++)
            value[i][j] = INF;
    scanf("%d%d", &n, &e);
    for (int i = 1; i <= e; i++)
    {
        cin >> x >> y >> weight;
        if (weight < value[x][y])
            value[y][x] = value[x][y] = weight;
    }
    prim(n);
    return 0;
}