prim算法

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

const int N = 550, INF = 0x3f3f3f3f;
int g[N][N], dist[N];
bool st[N];
int n, m;

int prim()
{
    memset(dist, 0x3f, sizeof dist);

    int res = 0;    //最小生成树里面所有边的长度之和
    for(int i = 0; i < n; i ++ )
    {
        int t = -1;

        //找到集合外的距离最小的边
        for(int j = 1; j <= n; j ++ )
                        // t == -1表示当前还没有找到任何一个点
            if(!st[j] && (t == -1 || dist[t] > dist[j]))    t = j;


        //如果不是第一个点，并且dist[t] = 正无穷，即这个点到集合的距离是正无穷，即当前这个图是不连通的。
        if(i && dist[t] == INF)     return INF;

        for(int j = 1; j <= n; j ++ )
            dist[j] = min(dist[j], g[t][j]);

        //只要不是第一个点，那这个dist[t]表示的就是当前这个点到已经连好的生成树里的某一条边的长度
        if(i)   res += dist[t];
        st[t] = true;
    }
    return res;
}

int main()
{
    cin >> n >> m;
    memset(g, 0x3f, sizeof g);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);    //无向图就是一种特殊的有向图，在建边的时候从a->b,b->a都建一条
    }

    int t = prim();

    if(t == INF)    puts("NO"); //  所有点不连通的时候就是不存在生成树
    else    cout << t << endl;

    return 0;
}

kruskal算法

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

const int N = 200010;
int p[N];
int n, m;

struct Edge
{
    int a, b, w;

    bool operator < (const Edge &W)const
    {
        return w < W.w;
    }
}edges[N];

int find(int x)
{
    if(p[x] != x)   p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i ++ )
    {
        int a, b, w;
        cin >> a >> b >> w;
        edges[i] = {a, b, w};
    }

    sort(edges, edges + m);
    for(int i = 1; i <= m; i ++ )   p[i] = i;

    int res = 0, cnt = 0;
    for(int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
        a = find(a), b = find(b);

        if(a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    if(cnt < n - 1) puts("NO");
    else    cout << res << endl;
    return 0;
}