并查集(Union Find)

并查集基础

一、概念及其介绍

并查集是一种树型结构,用于处理一些不相交集合的合并及查询问题。
并查集的思想是用一个数组表示了整片森林(parent),树的根节点唯一标识了一个集合,我们只要找到了某个元素的的树根,就能确定它在哪个集合里。
对于并查集主要支持两个操作:

  • 并{ union(p,q) }
  • 查找{ find(p) }
    来回答一个问题:

    连接{ inConnected(p, q) }

二、并查集的基本数据表示

难点分析:横向上的数值其实是对应横线下数据的在数组中的索引值,也就是说横线下是一个真正的数组,而横线上则是数组对应的索引,在这里我们是用索引当作元素,用数组数据值的异同来表示元素是否连接。

横线上:用数组索引表示元素
横线下:表示连接情况(值为0的表示在一个集合即连接)
所以0-4在同一个集合,5-9在同一个集合:
并查集(Union Find)

三、代码实现

下面我们来介绍并查集的主要操作:
我们先实现一个并查集:

#include <iostream>
#include <cassert>

using namespace std;

  // 我们的第一版Union-Find
namespace UF1 {

class UnionFind {

private:
  int *id;         // 第一版Union-Find本质就是一个数组
  int count;     // 数据个数

 public:
   // 构造函数
   UnionFind(int n) {
         count = n;
         id = new int[n];
 // 初始化, 每一个id[i]指向自己, 没有合并的元素,每一个数都是一个集合
        for (int i = 0; i < n; i++)
           id[i] = i;
 }

 // 析构函数
  ~UnionFind() {
        delete[] id;
  }
  1. find的实现:(查询元素所在的集合编号,直接返回数组值,O(1) 的时间复杂度。)

    // 查找过程, 查找元素p所对应的集合编号
    int find(int p) {
         assert(p >= 0 && p < count);
         return id[p];
    }
  2. isConnected的实现:

    // 查看元素p和元素q是否所属一个集合
    // O(1)复杂度
    bool isConnected(int p, int q) {
           return find(p) == find(q);
    }
  3. union的实现:(合并元素 p 和元素 q 所属的集合, 合并过程需要遍历一遍所有元素, 再将两个元素的所属集合编号合并,这个过程是 O(n) 复杂度。)

    // 合并元素p和元素q所属的集合
    // O(n) 复杂度
    void unionElements(int p, int q) {   //union在c++中是一个关键字,所以这里用 unionElements
    
         int pID = find(p);
         int qID = find(q);
    
         if (pID == qID)
              return;
    
    // 合并过程需要遍历一遍所有元素, 将两个元素的所属集合编号合并
         for (int i = 0; i < count; i++)
                 if (id[i] == pID)
                     id[i] = qID;
    }
本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!