本文共 2601 字，大约阅读时间需要 8 分钟。

Prim算法与Kruskal算法是最小生成树问题中两种常用的算法，各有其独特的实现方式和适用场景。本文将详细介绍这两种算法的实现方法。

Prim算法

Prim算法是一种贪心算法，通过不断选择权重最小的边来构建最小生成树。其核心思想是从图中随机选择一个起点，然后依次选择与当前树没有连接的边中权重最小的边，直到树包含所有顶点为止。

算法实现步骤

代码解读

#include 
   
    
using namespace std;
struct Edge {
    int to, val, nexty;
};
int head[5005], cnt;
void add(int u, int v, int val) {
    cnt++;
    edge[cnt].to = v;
    edge[cnt].val = val;
    edge[cnt].nexty = head[u];
    head[u] = cnt;
}
int dis[5005];
bool vis[5005];
struct node {
    int dis, num;
    bool operator<(const node &a) const {
        return dis > a.dis;
    }
};
priority_queue
    
      qu;
int n, m, a, b, c;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        dis[i] = 0x7fffffff;
    for (int i = 1; i <= m; i++) {
        cin >> a >> b >> c;
        add(a, b, c);
        add(b, a, c);
    }
    dis[1] = 0;
    int cnt = 0, sum = 0;
    qu.push(node{0, 1});
    while (!qu.empty() && cnt <= n) {
        node current = qu.top();
        qu.pop();
        if (vis[current.num]) continue;
        vis[current.num] = true;
        sum += current.dis;
        for (int e = head[current.num]; e; e = edge[e].nexty) {
            if (!vis[edge[e].to]) {
                dis[edge[e].to] = edge[e].val;
                qu.push(node{edge[e].val, edge[e].to});
            }
        }
        cnt++;
    }
}
    
   

Kruskal算法

Kruskal算法通过排序所有边，并按权重从小到大依次选择不形成环的边来构建最小生成树。其核心在于通过并查集数据结构来管理连通性，确保每次选择的边不会形成环。

算法实现步骤

代码解读

#include 
   
    
using namespace std;
int n, m;
struct Edge {
    int u, v, val;
};
bool cmp(Edge a, Edge b) {
    return a.val < b.val;
}
int fa[5005];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        fa[i] = i;
    for (int i = 1; i <= m; i++) {
        cin >> edge[i].u >> edge[i].v >> edge[i].val;
    }
    sort(edge + 1, edge + m + 1, cmp);
    int cnt = 0, sum = 0;
    for (int i = 1; i <= m; i++) {
        int uu = find(edge[i].u);
        int vv = find(edge[i].v);
        if (uu == vv) continue;
        fa[uu] = vv;
        cnt++;
        sum += edge[i].val;
        if (cnt == n - 1) break;
    }
    cout << sum;
}
   

总结

Prim算法和Kruskal算法均能有效解决最小生成树问题，但两者的实现方式和优化策略有所不同。Prim算法通过优先队列管理边的选择，适合处理边权重较多的场景；而Kruskal算法通过排序边并使用并查集，适合处理边较多的场景。在实际应用中，选择哪种算法往往需要根据具体问题的规模和边的密度来决定。

转载地址：http://pcef.baihongyu.com/