本文共 2522 字，大约阅读时间需要 8 分钟。
Prim算法与Kruskal算法是最小生成树问题中两种常用的算法，各有其独特的实现方式和适用场景。本文将详细介绍这两种算法的实现方法。
Prim算法是一种贪心算法，通过不断选择权重最小的边来构建最小生成树。其核心思想是从图中随机选择一个起点，然后依次选择与当前树没有连接的边中权重最小的边，直到树包含所有顶点为止。
#includeusing 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算法通过排序所有边，并按权重从小到大依次选择不形成环的边来构建最小生成树。其核心在于通过并查集数据结构来管理连通性，确保每次选择的边不会形成环。
#includeusing 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/