Kruskal算法简介

Kruskal算法的具体思路是，为了造出一棵最小生成树，我们从z最小边权的边开始，按边权从小到大依次加入，如果某次加边产生了环，就跳过选择这条边，直到加入了 n-1条边，即形成了一棵树。

证明：使用归纳法，证明任何时候Kruskal算法选择的边集都被某棵最小生成树所包含。
基础：对于算法刚开始时，显然成立（最小生成树存在）。
归纳：假设某时刻成立，当前边集为F，令T为这棵最小生成树，考虑下一条加入的边 e。
如果 e属于T  ，那么成立。
否则，T+e一定存在一个环，考虑这个环上不属于F的另一条边f （一定只有一条）。
首先，f的权值一定不会比 e小，不然f会在e之前被选取。
然后，f的权值一定不会比 e大，不然T+e-f就是一棵比T还优的生成树了。
所以，T+e-f包含了F，并且也是一棵最小生成树，归纳成立。

对于是否形成环，可以利用并查集进行判定。具体代码如下：

int find(int x){
            return (p[x]==x)? x: (p[x]=find(p[x]));
}

未开始选择边时，每一条边都独立于其它边存在，即：

for(int i=0; i<n; i++)
   p[i]=i;

根据边权对边进行排序：

bool cmp(const edge &p1, const edge &p2){
	return p1.w<p2.w;
}
sort(myedge, myedge+m, cmp);

开始选择及判定：

for(int i=0; i<m; i++){
	w=myedge[i].w;
	x=find(myedge[i].u);
    y=find(myedge[i].v);
	if(x!=y){                //不构成环时
		ans+=w;
	    counter++;
	    p[y]=x;
    	if(counter==n-1) break;  //形成树时完成选边
     }
 }

最小生成树基础拓展

Kruskal算法的核心思想是按照边权的升序选择不形成环的边加入树中，在实际问题中，我们所需要的可能不仅仅是最小生成树，而对选择的边有其他的要求，但Kruskal算法中对边按边权进行选择的思想仍然可以帮助我们解决问题。

以洛谷P2121 拆地毯为例:

会场上有 n 个关键区域，不同的关键区域由 m 条无向地毯彼此连接。每条地毯可由三个整数 u、v、w 表示，其中 u 和 v 为地毯连接的两个关键区域编号，w 为这条地毯的美丽度。
由于颁奖典礼已经结束，铺过的地毯不得不拆除。为了贯彻勤俭节约的原则，组织者被要求只能保留 K 条地毯，且保留的地毯构成的图中，任意可互相到达的两点间只能有一种方式互相到达。换言之，组织者要求新图中不能有环。现在组织者求助你，想请你帮忙>算出这 K 条地毯的美丽度之和最大为多少。

此题对最小生成树的算法存在两处拓展：
1、 需要的是边权和（美丽度之和）最大，因此需将边按边权降序排列；
2、 生成的不一定是最小生成树而是具有k条边的树，即任意两点之间不一定相通，但相通的两点之间一定不形成环。

由以上分析对Kruskal算法进行拓展，需要修改的是：

//边权按降序排列
     bool cmp(const edge &p1, const edge &p2){
            return p1.w>p2.w;
}
//加入k条边后即停止选择
if(counter==k) break;

修改以上两处后即可完成此题。具体实现代码：

#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n, m, k, ans, counter, p[N], x, y, w;

struct edge{
    int u, v, w;
}myedge[N];

bool cmp(const edge &p1, const edge &p2){
    return p1.w>p2.w;
}

int find(int x){
    return (p[x]==x)? x: (p[x]=find(p[x]));
}

int main(){
    scanf("%d%d%d", &n, &m, &k);
    for(int i=0; i<m; i++)
        scanf("%d%d%d", &myedge[i].u, &myedge[i].v, &myedge[i].w);
    for(int i=0; i<n; i++)
        p[i]=i;
    sort(myedge, myedge+m, cmp);
    for(int i=0; i<m; i++){
        w=myedge[i].w;
        x=find(myedge[i].u);
        y=find(myedge[i].v);
        if(x!=y){
            ans+=w;
            counter++;
            p[y]=x;
            if(counter==k) break;
        }
    }
    printf("%d", ans);
    return 0;
}

此外，还有洛谷P1991 无线通讯网：

国防部计划用无线网络连接若干个边防哨所。2 种不同的通讯技术用来搭建无线网络；
每个边防哨所都要配备无线电收发器；有一些哨所还可以增配卫星电话。
任意两个配备了一条卫星电话线路的哨所（两边都有卫星电话）均可以通话，无论他们相距多远。而只通过无线电收发器通话的哨所之间的距离不能超过 D，这是受收发器的功率限制。收发器的功率越高，通话距离 D 会更远，但同时价格也会更贵。
收发器需要统一购买和安装，所以全部哨所只能选择安装一种型号的收发器。换句话说，每一对哨所之间的通话距离都是同一个 D。你的任务是确定收发器必须的最小通话距离 D，使得每一对哨所之间至少有一条通话路径（直接的或者间接的）。

此题为最小生成树的变形，建造卫星电话即可构造0权边，显然应选取边权较大的两点构造0权边，故可采用Kruskal算法并少选取x条边；
对于s个点，x=s-1，证明如下：

1、若这s个点构成一棵树，显然成立；
2、若这s个点不构成树，设形成了n个联通分支，则已可以删去（s-n-1）条边；
在任意两个联通分支中选择两根结点，这两点及其之间的路径可构成一个环（把这两个点视为同一个点），则在该环中，一定可以删去一条边，该边满足连接两端点的路径中通过两个根结点的点的路径大于原路径，那么又要删去n条边，则总共仍要删去(s-1)条边；
那么需要构造的是有(p-1)-(s-1)=p-s条边的生成树，剩下的点用卫星电话连接即可。

在代码实现时，只需将停止加边的条件改为

if(counter==(p-s)) break;

即可。具体实现代码：

#include<bits/stdc++.h>
using namespace std;
#define N 1005
int n, m, p[N], cnt=0, x, y, counter;
double sum, value;
struct Node{
    int x, y;
}node[N];

struct edge{
    int u, v;
    double value;
}myedge[N*N];

bool cmp(const edge &p1, const edge &p2){
    if(p1.value==p2.value) return p1.u<p2.u;
    return p1.value<p2.value;
}

int find(int x){
    return (p[x]==x)? x : (p[x]=find(p[x]));
}

double len(int u, int v){
return (double)sqrt((double)(node[v].x-node[u].x)*(node[v].x-node[u].x)+(double)(node[v].y-node[u].y)*(node[v].y-node[u].y));
} 
int main(){
    scanf("%d%d", &n, &m);
    for(int i=1; i<=n; i++){
       scanf("%d%d", &node[i].x, &node[i].y);
       p[i]=i;
    }
    for(int i=1; i<n; i++){
        for(int j=i+1; j<=n; j++){
            myedge[cnt].u=i;
            myedge[cnt].v=j;
            myedge[cnt++].value=len(i, j);
        }
    }
    for(int i=0; i<m; i++){
        scanf("%d%d", &myedge[cnt].u, &myedge[cnt].v);
        myedge[cnt++].value=0.0;
    }
    sort(myedge, myedge+cnt, cmp);
    for(int i=0; i<cnt; i++){
        value=myedge[i].value;
        x=find(myedge[i].u);
        y=find(myedge[i].v);
        if(x!=y){
            sum+=value;
            p[y]=x;
            counter++;
            if(counter>=n-1) break;
        }
    }
    printf("%.2lf", sum);
    return 0;
}