C++怎么实现基于不相交集合的kruskal算法

这篇文章主要介绍“C++怎么实现基于不相交集合的kruskal算法”，在日常操作中，相信很多人在C++怎么实现基于不相交集合的kruskal算法问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”C++怎么实现基于不相交集合的kruskal算法”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

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

不相交集合的数据结构

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

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)

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表示顶点数

知识补充

乘胜追击一下，通过一个例题再深入了解一下kruskal 算法吧

思路：就是最小生成树啊

代码

#include<iostream>#include<algorithm>#include<cstring>#include<cstdio>#include<vector>using namespace std;#define INTMAX 0x3f3f3f3ftypedef pair<int,int> pii;typedef long long ll;#define x first#define y secondint rank[505];int father[505];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]++;    }}struct edge{    int fr,to,w;};int num_case,num_v,result;vector<edge> arr_edge;void debug(){    for(int i=0;i<arr_edge.size();i++)    {        cout<<arr_edge[i].fr<<" to "<<arr_edge[i].to<<"="<<arr_edge[i].w<<endl;    }}void init(){    arr_edge.clear();    result=0;}void input(){    int w;    scanf("%d",&num_v);    for(int i=0;i<num_v;i++)    {        for(int j=0;j<num_v;j++)        {            scanf("%d",&w);            if(i<j)            {                edge temp;                temp.fr=i;                temp.to=j;                temp.w=w;                arr_edge.push_back(temp);            }        }    }}bool mycompare(const edge& x,const edge &y){    return x.w<y.w;}void kruskal(){    for(int i=0;i<num_v;i++)father[i]=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=max(result,w);            simply_union_set(fr,to);        }    }}void solve(){    init();    input();    //debug();    kruskal();    cout<<result<<endl;}int main(){    scanf("%d",&num_case);    while(num_case--)    {        solve();    }    return 0;}

到此，关于“C++怎么实现基于不相交集合的kruskal算法”的学习就结束了，希望能够解决大家的疑惑。理论与实践的搭配能更好的帮助大家学习，快去试试吧！若想继续学习更多相关知识，请继续关注编程网网站，小编会继续努力为大家带来更多实用的文章！