C++实现基于不相交集合的O(mlgn)复杂度的kruskal算法

本文实现完全参考<<Introduction to Algorithms Third edition>>,

不相交集合的数据结构

我们采用森林的方式实现不相交集合。这个森林是极简化的,每个节点只有一个指向父亲的指针,而且森林中的每一颗树都是一个集合,我们取树的根节点为这个集合的代表元。

int rank[505];
int father[505];
void make_set(int x)
{father[x]=x;rank[x]=0;
}
int find_set(int x)
{if (x!=father[x]){father[x]=find_set(father[x]);}return father[x];
}
void simply_union_set(int u,int v)
{u=find_set(u);v=find_set(v);father[u]=v;
}
void  perfect_union_set(int u,int v)
{u=find_set(u);v=find_set(v);if (rank[u]>rank[v]){father[v]=u;}else{father[u]=v;if(rank[u]==rank[v])rank[v]++;}}

可以看到在find_set()函数中采用了两趟遍历的思想,第一趟遍历找的根节点,第二趟遍历将路径上的节点全部指向根节点,完成了压缩树高。

在实现集合合并的时候,我们采用了两种方法:一种方法是直接合并simply_union_set,另一种是采用按秩合并的思想perfect_union_set,即总是让秩小合并到秩大的集合中,这是一种减少树高的有效策略;

当我们采用按秩合并时时,上述每一个操作的最差时间复杂度,都约等于$O(1)$
详情见<<Introduction to Algorithms Third edition>>中证明

kruskal 算法

void kruskal()
{for(int i=0;i<num_v;i++)make_set(i);sort(arr_edge.begin(),arr_edge.end(),mycompare);for(int i=0;i<arr_edge.size();i++){int fr=arr_edge[i].fr;int to=arr_edge[i].to;int w=arr_edge[i].w;if( find_set(fr)!=find_set(to)){result+=w;perfect_union_set(fr,to);}}
}

kruskal 算法是一种基于贪心策略的算法,它的时间复杂度的最大开销就是排序算法,即$O(mlgm)=O(mlgn)$,这里m表示边数,n表示顶点数