最小生成树（Kruskal）

最小生成树有两种解法，分别是Prim算法和Kruskal算法。在这篇文章我将会讲解Kruskal算法。

1.简介

Kruskal算法是一种贪心算法，分为三个步骤：按权值排序、找father(父节点)和主算法。

2.代码

1.按权值排序

int n,m;
//定义struct
struct edge{
	int u,v,w;
} e[100005];

bool cmp(edge x, edge y) return x.w < y.w;//按权值升序排序

2.找father(父节点)

int f[100005];
int FF(int x){
	while (x != f[x]){
    	f[x] = f[f[x]];
        x = f[x];
    }
    return x;
}

3.主算法（包括输入输出）

void kruskal