Kruskal算法

算法思想

前置算法-并查集

将所有边依据边权进行排序，从边权最小的边开始枚举，利用并查集判断这条边的两个点是否已经连通，如果已经连通，就跳过这条边，当已经连了n-1条边，说明已经求出了最小生成树。

Code-C++

#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2e5 + 10, inf = 0x3f3f3f3f;

struct Edge
{
    int a, b, c;
}edges[maxn];
int n, m;
int f[maxn];

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

bool cmp(Edge a, Edge b)
{
    return a.c < b.c;
}

int kurskal()
{
    for (int i = 1; i <= n; i++) f[i] = i;
    int res = 0, cnt = 0;
    sort(edges ,edges + m , cmp);
    for (int i = 0; i < m; i++)
    {
        int a = find(edges[i].a), b = find(edges[i].b);
        if (a != b)
        {
            res += edges[i].c;
            f[a] = b;
            cnt++;
        }
        if (cnt == n - 1) return res;
    }
    return inf;

}

int main()
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> edges[i].a >> edges[i].b >> edges[i].c;
    }
    int t = kurskal();
    if (t == inf) cout << "orz" << endl;
    else cout << t << endl;
    return 0;
}

Prim算法

算法思想

与dijkstra求最短路相似，从起点开始连接距离最短的点，不同的是每次最短的距离是所有不连通的点和已经连通的图之间的最短距离，每次更新一个点，所以这些距离也就可以只更新每一次更新的点相连的点的距离。

Code-C++

#include <iostream>
#include <cstring>

using namespace std;

const int maxn = 5050, inf = 0x3f3f3f3f;

int n, m;
int g[maxn][maxn];
int dist[maxn];
bool vis[maxn];

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++)
        {
            if (!vis[j] && (t == -1 || dist[t] > dist[j]))
            {
                t = j;
            }
        }
        if (i && dist[t] == inf) return inf;
        if (i) res += dist[t];
        vis[t] = true;
        for (int j = 1; j <= n; j++)
        {
            dist[j] = min(dist[j], g[t][j]);
        }
    }
    return res;
}

int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> n >> m;
    while (m--)
    {
        int a, b, c;
        cin >> a >> b >> c;
        g[a][b] = g[b][a] = min(g[a][b], c);
    }
    auto t = prim();
    if (t == inf) cout << "orz" << endl;
    else cout << t << endl;
    return 0;
}