• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

并查集的数组实现(C++) (原创)

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

摘要:本文简要介绍了并查集的基本原理,并且给出了简单易于理解的数组实现。本文给出的实现方法

使用数组而不是通用的树结构,是为了方便对并查集的理解,其合并的时间复杂度是O(N),不适合高效

的应用。高效的并查集实现请参见博文《并查集的树形实现》。

关键字:并查集,Union,Find,Set,UnionFind

并查集是一个通用的数据结构,经典的应用有最小生成树的Kruskal算法。该结构可用于判断元素所

在的集合以及合并不相交的集合。一般并查集有三个主要的方法:

一是初始化,UnionFindSet_Init(int n),用于初始化并查集。

二是查找一个元素所在的集合,UnionFindSet_Find(int x),查找元素X。

三是合并两个元素所在的集合,UnionFindSet_Merge(int x, int y)。

本文给出的实现中使用一个数组UnionFindSet[N]保存所有可能出现的元素,UnionSetFind[i]表示元素

i所在的集合编号,同一集合中的元素集合编号相同且唯一。首先将所有元素视为孤立的集合,为每个元素

设置一个集合编号;当合并某两个元素所在的集合A和B时,将一个集合中的所有元素的集合编号设置为另

一个集合的元素编号;当查找某个元素所在的集合编号是,返回UnionSetFind[i]即可。

以上思想的C++实现如下:


/*
 *并查集的数组实现
 */

//实现方法一,数组
//INIT时间复杂度,O(N)
//FIND时间复杂度,O(1)
//Merge时间复杂度,O(N)

#include <iostream>

using namespace std;

#define N 1000

int UnionFindSet[N];

void uf_init(int n); //初始化并查集,每个点都是一个集合
int uf_find(int x); //在并查集中查找一个元素,返回集合编号
void uf_merge(int x, int y, int n); //合并两个元素所在的集合

int main(int argc, char* *argv)
{
      int n = 20;
      uf_init(n);
      uf_merge(1, 3, n);
      uf_merge(2, 3, n);
      uf_merge(4, 5, n);
      uf_merge(10, 13, n);
      uf_merge(4, 13, n);
      if(uf_find(1) == uf_find(3))
      {
            cout<<"success1"<<endl;
      }
      if(uf_find(5) == uf_find(10))
      {
            cout<<"success2"<<endl;
      }
      if(uf_find(1) != uf_find(4))
      {
            cout<<"success3"<<endl;
      }
      system("pause");
      return 0;
}

void uf_init(int n)
{
      //时间复杂度O(N)
      for(int i = 0; i < n; ++i)
            UnionFindSet[i] = i;
}

int uf_find(int x) //ensure x>=0 && x < n
{
      //时间复杂度O(1)
      return UnionFindSet[x];
}

void uf_merge(int x, int y, int n)//ensure x,y>=0 && x,y < n
{
      //时间复杂度O(N)
      int set_id1 = UnionFindSet[x];
      int set_id2 = UnionFindSet[y];
      for(int i = 0; i < n; ++i)
            if(UnionFindSet[i] == set_id1)
                  UnionFindSet[i] = set_id2;
}

鲜花

握手

雷人

路过

鸡蛋
专题导读
上一篇:
并查集的树形实现(C++)(原创)发布时间:2022-05-14
下一篇:
单件模式的c++实现发布时间:2022-05-14
热门推荐
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap