Kruskal算法
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
- 把图中的所有边按代价从小到大排序；
- 把图中的n个顶点看成独立的n棵树组成的森林；
- 按权值从小到大选择边，所选的边连接的两个顶点ui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
- 重复(3),直到所有顶点都在一颗树内或者有n-1条边为止。
以下伪代码：
把所有的边排序，记住第i小的边为e[i](i<=i<m)
初始化MST为空
！！初始化连通分量，让每个点自成为一个独立的连通分量
for(int i = 0; i < m; i++){
if(e[i].u和e[i].v不在同一个连通分量){
把边e[i]加入MST
合并e[i].u和e[i].v所在的连通分量
}
}
在上面的伪代码中，最关键的地方在于连通分量的查询与合并：
- 1 需要知道任意两个点是否在同一个连通分量中
-
2 还需要合并两个连通分量
最容易想到的方法就是“暴力”，即每次合并时只在MST中加入一条边，若用邻接矩阵，则可以简单地合并，但是查询则需要暴力搜索且效率不高。
故引入并查集，代码如下：
来自kuangbin的模板
2.2 Kruskal 算法
/* * Kruskal算法求MST */
const int MAXN=110;//最大点数
const int MAXM=10000;//最大边数
int F[MAXN];//并查集使用
struct Edge { int u,v,w; }edge[MAXM];//存储边的信息，包括起点/终点/权值
int tol;//边数，加边前赋值为0
void addedge(int u,int v,int w) {
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b) {//排序函数，讲边按照权值从小到大排序
return a.w<b.w;
}
int find(int x) {
if(F[x]==-1)return x;
else return F[x]=find(F[x]);
}
int Kruskal(int n)//传入点数，返回最小生成树的权值，如果不连通返回-1
{
memset(F,-1,sizeof(F));
sort(edge,edge+tol,cmp);
int cnt=0;//计算加入的边数
int ans=0;
for(int i=0;i<tol;i++) {
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if(t1!=t2) {
ans+=w;
F[t1]=t2;
cnt++;
}
if(cnt==n-1)break;
}
if(cnt<n-1)return -1;//不连通
else return ans;
}
刘汝佳在《入门经典》中的k树算法用了一个间接排序，亦值得借鉴
