主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
Kruskal
最后更新于 2025-08-28 16:15:29
作者
yyycj
分类
算法·理论
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
Kruskal 是用来求生成树的一种算法。 给你一个图，要求删除一些边，使这个图成为一棵树，并让所有边的总和最小，成为这个图的最小生成树；反之则为最大生成树。 Kruskal 算法基于并查集，如果要求最小生成树就将所有边按权值从小到大排序；否则从大到小排序。随后遍历边，此时考虑是否将这条边保留在原图中，如果这条边的起点与终点处在一棵树上，就无需保留；否则因为排过序，为了保持树的连通一定是越往前的保留越好，并将起点与终点连到一棵树上。 代码： ```cpp sort(edge + 1, edge + m + 1, cmp); int cnt = 0, ans = 0; for (int i = 1; i <= n; i++) fa[i] = i; for (int i = 1; i <= m; i++) { if (_find(edge[i].u) == _find(edge[i].v)) continue; cnt++; ans += edge[i].w; _merge(edge[i].u, edge[i].v); } ```
正在渲染内容...
点赞
0
收藏
0
