Bor?vka 算法求 MST 最小生成树
2021-07-15 16:05
阅读：374
标签：cpp continue gif bre r++ wiki 索引 处理 join 基本思路：用定点数组记录每个子树的最近邻居。对于每一条边进行处理：如果这条边连成的两个顶点同属于一个集合，则不处理，否则检测这条边连接的两个子树，如果是连接这两个子树的最小边，则更新 (合并)。时间复杂度平均 \(O(V+E)\)，最坏 \(O((V+E)\log V)\)。 下面是 Bor?vka 算法演示动图：（源：Wikimedia） 程序代码： Bor?vka 算法求 MST 最小生成树 标签：cpp continue gif bre r++ wiki 索引 处理 join 原文地址：https://www.cnblogs.com/greyqz/p/9536352.html
struct node {int x, y, w; } edge[M];
int d[N]; // 各子树的最小连外边的权值
int e[N]; // 各子树的最小连外边的索引
bool v[M]; // 防止边重复统计
int fa[N];
int find(int x) {return x==fa[x] ? x : (fa[x]=find(fa[x])); }
void join(int x, int y) {fa[find(x)]=find(y); }
int Boruvka() {
int tot=0;
for (int i=1; i
评论
亲，登录后才可以留言！