【数据结构与算法】最小生成树Kruskal

1.#include iostream #include algorithm #include vector using namespace std; struct Edge { int u, v, w; // 起点终点边权 }; vectorEdge edges; vectorint parent; // 比较函数按边权升序排列 bool compareEdge(Edge a, Edge b) { return a.w b.w; // 小于号是升序大于号是降序 } // 并查集查找 int find(int x) { if (parent[x] ! x) parent[x] find(parent[x]); return parent[x]; } int main() { int N, M; cin N M; edges.resize(M); for (int i 0; i M; i) { cin edges[i].u edges[i].v edges[i].w; } // 使用比较函数排序 sort(edges.begin(), edges.end(), compareEdge); // 初始化并查集 parent.resize(N 1); for (int i 1; i N; i) { parent[i] i; } long long totalWeight 0; int edgesUsed 0; // Kruskal算法主循环 for (int i 0; i M; i) { int u edges[i].u; int v edges[i].v; int w edges[i].w; // 找到两个节点的根 int rootU find(u); int rootV find(v); // 如果不在同一集合加入生成树 if (rootU ! rootV) { parent[rootU] rootV; // 合并集合 totalWeight w; edgesUsed; // 已选够N-1条边结束 if (edgesUsed N - 1) { break; } } } // 输出结果 if (edgesUsed N - 1) { cout totalWeight endl; } else { cout orz endl; } return 0; }最小生成树Kruskal模板题详解并查集 贪心一次搞懂这道题是最标准的最小生成树模板题模型非常明确给你一个无向图选出若干条边把所有点连起来并且让总权值最小如果无法连通就输出 orz这种题基本可以一眼锁定 Kruskal 算法。Kruskal 的核心思想就是贪心按边权从小到大排序然后一条一条尝试加入如果这条边连接的两个点原本不连通就加入如果已经连通了再加就会形成环就跳过最终选出 n-1 条边就是最小生成树。先用结构体 Edge 存边再用 sort 按权值升序排序然后用并查集维护连通性parent 数组记录每个点的“祖先”find 函数带路径压缩可以加速查找在主循环中每次取一条边 (u, v, w)判断 find(u) 和 find(v) 是否相同如果不同就合并集合并把权值加入答案同时计数 edgesUsed。这里最关键的一步是“判环”并查集的作用就是判断两个点是否已经在同一个连通块中如果是就说明这条边会形成环必须跳过如果不是就说明这条边是“有用的”可以放心加入这也是 Kruskal 能保证正确性的核心。还有一个重要细节是终止条件当选的边数达到 N-1 时就可以提前结束因为最小生成树一定只有 N-1 条边最后再判断 edgesUsed 是否等于 N-1如果不是说明图不连通输出 orz。从直观上理解这个算法你可以想象在“修路”每次优先修最便宜的路但前提是这条路能连接两个原本不连通的区域最终用最少的钱把所有城市连起来这就是最小生成树的本质。总结一句Kruskal 边排序 并查集判环 贪心选边只要看到“无向图 连通所有点 权值最小”基本就是这一套模板熟练之后可以秒写。并查集朴素int parent[100]; // parent[i]表示i的父节点 // 初始化每个节点自成一家 void init(int n) { for (int i 1; i n; i) { parent[i] i; // 自己是自己的父亲 } } // 查找找根节点朋友圈老大 int find(int x) { while (parent[x] ! x) { x parent[x]; // 一直向上找 } return x; } // 合并把x和y所在集合合并 void unionSet(int x, int y) { int rootX find(x); int rootY find(y); if (rootX ! rootY) { parent[rootX] rootY; // 让一个根指向另一个根 } }路径压缩优化一个根下直接连接好多节点直接不压缩查找可能 O(n)压缩后查找接近 O(1)int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 递归压缩 } return parent[x]; } // 或者非递归版本 int find(int x) { int root x; while (parent[root] ! root) { root parent[root]; // 先找到根 } // 路径压缩把路径上所有节点直接连到根 while (parent[x] ! root) { int temp parent[x]; parent[x] root; x temp; } return root; }int find(int x) { if (parent[x] ! x) { // 如果x不是根节点 parent[x] find(parent[x]); // 递归找根并压缩路径 } return parent[x]; // 返回根节点 }假设树结构1→2→3→44是根初始parent[1]2, parent[2]3, parent[3]4, parent[4]4 调用 find(1):find(1): parent[1]2≠1 → 进入if parent[1] find(parent[1]) find(2) // 先递归 find(2): parent[2]3≠2 → 进入if parent[2] find(parent[2]) find(3) // 递归 find(3): parent[3]4≠3 → 进入if parent[3] find(parent[3]) find(4) // 递归 find(4): parent[4]4 → 返回4 // 回到find(3): parent[3] 4, 返回4 // 回到find(2): parent[2] 4, 返回4 // 回到find(1): parent[1] 4, 返回4递归前 递归后 1 1 ↓ ↓ 2 4 ↓ ↗ ↖ 3 2 3 ↓ 4 (根)合并二、合并过程分解 步骤1分别找根同时压缩 cpp int rootX find(2); // 返回4同时2→4已经是4int rootY find(6); // 返回7同时6→7已经是7 步骤2合并根节点 cpp parent[rootX] rootY; // parent[4] 7 步骤3结果 text 合并后 原集合A1→4, 2→4, 3→4, 4→7 ← 4现在指向7 原集合B5→7, 6→7, 7→7 现在结构 1→4→7 2→4→7 3→4→7 5→7 6→7 7→7根 三、合并后的压缩效果 下次查询时的压缩 如果现在查询节点1 cpp find(1): 初始1→4→7 递归parent[1]4≠1 → parent[1]find(4)find(4): parent[4]7≠4 → parent[4]find(7)find(7): parent[7]7 → 返回7 回到find(4): parent[4]7, 返回7 回到find(1): parent[1]7, 返回7 结果1→7, 4→7路径压缩了 最终完全压缩状态 多次查询后所有节点都直接指向根7 text 1→7 2→7 3→7 4→7 5→7 6→7 7→7确保联通二、为什么 N-1 条边表示连通 图论定理 对于一个有 N 个节点的无向连通图 它的最小生成树恰好有 N-1 条边 如果能选出 N-1 条边连接所有节点 → 图是连通的 如果选不出 N-1 条边 → 图不连通有多个连通分量 直观理解 想象用边把 N 个点连接起来 每连接一个点需要 1 条边 连接 N 个点最少需要 N-1 条边 如果连 N-1 条边都凑不齐说明有些点根本连不上 三、Kruskal算法如何保证判断正确 算法执行过程 cpp int edgesUsed 0; // 已选边数计数器for (int i 0; i M; i) {if (find(u) ! find(v)) { // 如果两点不在同一连通块unite(u, v); // 合并连通块 totalWeight w; edgesUsed; // 计数1if (edgesUsed N - 1) break; // 够了就停}} 两种情况 情况1图连通 text 节点: 1-2-3-4 (共4个节点) 需要的边: 3条 (N-13) 算法过程: 选边(1,2) → edgesUsed1 选边(1,3) → edgesUsed2 选边(1,4) → edgesUsed3 → 停止 最后 edgesUsed 3 N-1 ✓ 情况2图不连通 text 节点: 1-2 3-4 (两个连通分量共4个节点) 最大能选的边: 只能选2条 (1-2, 3-4) 算法过程: 选边(1,2) → edgesUsed1 选边(3,4) → edgesUsed2 再没有边能连接两个分量了 最后 edgesUsed2 N-13 → 不连通2.#includebits/stdc.h using namespace std; int N,M; typedef struct edge{ int u,v,w; }edge; vectorboolenemy; vectorintparent; vectoredgeedges; int find(int x) { if(parent[x]!x) { parent[x]find(parent[x]); } return parent[x]; } bool compare(edge a,edge b) { return a.wb.w; } int main() { cinNM; parent.resize(N); for(int i0;iN;i) parent[i]i; enemy.resize(N,false); for(int i0;iM;i) { int city; cincity; enemy[city]true; } edges.resize(N-1); long long weight0; for(int i0;iN-1;i) { cinedges[i].uedges[i].vedges[i].w; weightedges[i].w; } sort(edges.begin(),edges.end(),compare); long long keep0; for(int i0;iN-1;i) { int uedges[i].u; int vedges[i].v; int wedges[i].w; int rootufind(u); int rootvfind(v); if(!(enemy[rootu]enemy[rootv])) { keepw; if(rootv!rootu) { parent[rootv]rootu; enemy[rootu]enemy[rootv]||enemy[rootu]; } } } coutweight-keependl; }#includebits/stdc.h using namespace std; typedef struct edge{ int u,v,w; }Edge; vectorEdgeedges; vectorintparent; int find(int x) { if(parent[x]!x) { parent[x]find(parent[x]); } return parent[x]; } bool compare(Edge a,Edge b) { return a.w b.w; } int main() { int N,K;cinNK; edges.resize(N-1); parent.resize(N); long long weight0; vectorboolenemy(N,false); for(int i0;iK;i) { int city;cincity; enemy[city]true; } for(int i0;iN-1;i) { cinedges[i].uedges[i].vedges[i].w; weightedges[i].w; } sort(edges.begin(),edges.end(),compare); for(int i0;iN;i) { parent[i]i; } long long keep0; for(int i0;iN-1;i) { int uedges[i].u; int vedges[i].v; int wedges[i].w; int rootufind(u); int rootvfind(v); if(!(enemy[rootu]enemy[rootv])) { keepw; if(rootu!rootv) { parent[rootu]rootv; enemy[rootv]enemy[rootu]||enemy[rootv]; } } } coutweight-keependl; return 0; }树上“隔离敌人”问题详解反向Kruskal思想这道题本质不是普通最小生成树而是树上删边问题因为原图已经是一棵树N 个点 N-1 条边所以不存在“选边连通”而是要“删边分裂”目标是让所有敌人所在的城市互相不连通并且删除代价最小。关键转化思路是与其考虑删哪些边不如考虑保留哪些边因为总权值是固定的删掉的最小 总权值 - 保留的最大于是问题变成在保证“每个连通块最多只有一个敌人”的前提下让保留下来的边权值之和最大。这样就变成一个典型的贪心优先保留权值大的边所以要对边按权值从大到小排序这就是你代码里 compare 写成 a.w b.w 的原因然后用并查集维护连通块同时用 enemy 数组标记这个集合里是否已经有敌人。遍历每一条边 (u, v, w)找到它们的根 rootu 和 rootv如果这两个集合“合并后不会出现两个敌人”也就是不能出现“两个集合都有敌人”那么这条边可以保留并进行合并否则就不能保留相当于把这条边删掉在合并时要同步更新 enemy[root]表示这个新集合是否含敌人。最终 keep 表示保留下来的最大权值和而答案就是 totalWeight - keep。这个问题的本质其实可以一句话总结在树上做“限制条件下的最大生成森林”和普通 Kruskal 的区别只是普通是避免成环这里是避免“一个集合里出现多个敌人”。总结一下核心套路树上问题先想“删边还是留边”删边最小 → 转成留边最大留边最大 → 反向 Kruskal从大到小选再配合并查集 状态标记enemy这类题基本都是这个思路一旦理解这个转化就会非常清晰。