图的最小生成树算法代码

最小生成树算法是解决图论中最重要的问题之一，它的主要目的是在给定的带权无向图中，找到一棵生成树，使得这棵树的所有边的权值之和最小。常用的算法有 Prim 算法和 Kruskal 算法。

下面是 Prim 算法的代码示例（C++实现）：

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

int head[MAXN], ver[MAXN << 1], edge[MAXN << 1], Next[MAXN << 1], tot;
int n, m, dis[MAXN];
bool vis[MAXN];

void add(int x, int y, int z) {
    ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
}

void prim(int s) {
    memset(dis, INF, sizeof(dis));
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
    q.push(make_pair(0, s));
    dis[s] = 0;
    while (!q.empty()) {
        int x = q.top().second;
        q.pop();
        if (vis[x])
            continue;
        vis[x] = true;
        for (int i = head[x]; i; i = Next[i]) {
            int y = ver[i], z = edge[i];
            if (dis[y] > z && !vis[y]) {
                dis[y] = z;
                q.push(make_pair(dis[y], y));
            }
        }
    }
}

下面是 Kruskal 算法的代码示例（C++实现）：

const int MAXN = 100010;
const int INF = 0x3f3f3f3f;

int fa[MAXN], n, m;
struct Edge {
    int x, y, w;
} e[MAXN];

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

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

void kruskal() {
    sort(e + 1, e + m + 1, cmp);
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    int cnt = 0, ans = 0;
    for (int i = 1; i <= m; i++) {
        int x = find(e[i].x), y = find(e[i].y), z = e[i].w;
        if (x != y) {
            fa[x] = y;
            ans += z;
            cnt++;
        }
        if (cnt == n - 1)
            break;
    }
}