Kruskal

Kruskal算法
此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。

1. 把图中的所有边按代价从小到大排序；
2. 把图中的n个顶点看成独立的n棵树组成的森林；
3. 按权值从小到大选择边，所选的边连接的两个顶点ui,vi,应属于两颗不同的树，则成为最小生成树的一条边，并将这两颗树合并作为一颗树。
4. 重复(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树算法用了一个间接排序，亦值得借鉴