文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

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

2023-02-22 15:00

关注

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

知识补充

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

题目:http://poj.org/problem?id=2485

思路:就是最小生成树啊

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;
#define INTMAX 0x3f3f3f3f
typedef pair<int,int> pii;
typedef long long ll;
#define x first
#define y second

int 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++实现基于不相交集合的O(mlgn)复杂度的kruskal算法的文章就介绍到这了,更多相关C++ kruskal算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯