最小生成树 Kruskal 算法

Kruskal 算法

edge存储边起点、终点、边权

fa[x]存储x的父节点

1、先初始化父节点

2、按边的权排序(贪心思想)

3、如果不在同一集合内，把这条边加入最小生成树，并且合并两个集合，反之就跳过

4、最后根据连接的点是否是顶点的个数减一确定能否生成最小生成树

如下图，红色表示取的边和次序，先取最小的2，再3，再4最后5，此时成为生成树，并且为最小生成树

核心代码：

//存储边和权
struct edge {int u, v, w;//重载运算符，排序时使用bool operator<(const edge& t) { return w < t.w; }
}e[N];
//并查集
int fa[N];
//     输入时要用uvw，n为顶点数，m为边数，cnt为当前已经连上的边
int ii,u, v, w,       n,    m,  cnt = 0;
int ans = 0;
//并查集寻父
int find(int x) {if (fa[x] == x)return x;else return fa[x] = find(fa[x]);
}
bool kruskal() {//先排序sort(&e[1], &e[1 + m]);int x, y;rep(ii, 1, m + 1) {x = find(e[ii].u);y = find(e[ii].v);//如果不在同一集合中if (x != y) {//合并集合fa[x] = y;cnt++;ans += e[ii].w;}}if (cnt == n - 1) return true;return false;
}

例题：

口袋的天空https://www.luogu.com.cn/problem/P1195