对克鲁斯卡尔算法的深度理解

之前对于克鲁斯卡尔算法的学习我只是草草地翻阅了《大话数据结构》的内容，也就会在纸上手动画一下用它来实现最小生成树的过程，至于算法的代码并没有认真去理解，而用到它的时候也只是对着书上的模板敲一敲。

暑期集训的时候正好出了一道克鲁斯卡尔的模板题，我心中暗喜，摩拳擦掌，三下五除二地把模板敲上去，静静地等待Accepted：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef struct//构造边集数组的元素类型
{
    int begin;
    int end;
    int weight;
}Edge;

Edge edges[1000005];
int parent[1000005];
int n,m;

int cmp(Edge a, Edge b)//快速排序的条件
{
    return a.weight < b.weight;
}

int Find(int f)//寻找根节点
{
    while(parent[f]>0)
        f=parent[f];
    return f;
}

int Kruskal()
{
    int sum=0;
    sort(edges,edges+m,cmp);//对边集数组按权值由小到大排序
    int i;
    for(i=0;i<n;++i) parent[i]=0;//初始化parent数组
    int x,y;
    for(i=0;i<m;++i)
    {
        x=Find(edges[i].begin);//寻找边edges[i]的“首节点”所在树的树根
        y=Find(edges[i].end);  //寻找边edges[i]的“尾节点”所在树的树根
        if(x!=y)               //假如x与y不等，说明两个顶点不在一棵树内，因此这条边的加入不会使已经选择的边集产生回路
        {
            parent[x]=y;
            sum+=edges[i].weight;
        }
    }
    return sum;
}

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<m;++i)
        scanf("%d%d%d",&edges[i].begin,&edges[i].end,&edges[i].weight);
    printf("%d\n",Kruskal());
    return 0;
}

然而评测姬反馈给我的却是Time Limit Exceeded……QAQ

苦思冥想了一会儿，还是没有什么头绪，就去百度了一下别人克鲁斯卡尔的算法是怎么写的。

仔细对比了一下我与他人代码的差别，大致上都一样，但对于用parent数组寻找根节点的处理却有所不同。

我是按照《大话》提供的代码写的：

for(i=0;i<n;++i) parent[i]=0;//初始化
int Find(int f)
{
    while(parent[f]>0)
        f=parent[f];
    return f;
}

其他人多是这样写的：

for(i=1;i<=n;i++)  parent[i]=i;//初始化
int Find(int f)
{
    if(parent[f]!=f)
        parent[f]=Find(parent[f]);
    return parent[f];
}

虽然形式有所不同，可是看上去貌似没什么差别呀……（原谅我太菜了）

难道这就是超时的问题所在？我把这一部分改了一下，提交，果然就AC了。

问了问dalao们，他们给的答复就是：第一种写法没有进行路径压缩 ，所以肯定会超时。

所谓路径压缩 ，是并查集里的一种操作。

第一种写法，只是在路径上不断地寻找上一个节点的父亲节点，一步一步地找到根节点。

而第二种路径压缩，实际上是在找完根结点之后，在递归回来的时候顺便把路径上元素的父亲指针都指向根结点。这样的话，虽然第一次寻找根节点也是一个一个地找，但是之后如果再次对这条路径上的某个节点进行操作，则可以一次性直接找到它的根节点，节省了大量的时间。

我这时才恍然大悟，原来克鲁斯卡尔算法中最关键的一步（判断是否形成回路），是用并查集的思想来实现的。