| RMVL 2.4.0 Robotic Manipulation and Vision Library

载入中...
搜索中...
未找到
Public 类型 | Public 成员函数 | Protected 成员函数 | Protected 属性 | 所有成员列表
rm::UnionFind< Tp > 模板类 参考
数学、算法模块 » 数据结构

并查集 更多...

`#include <rmvl/algorithm/datastruct.hpp>`

rm::UnionFind< Tp > 的协作图:

## Public 类型
typedef Tp | value_type
typedef Tp & | reference
typedef const Tp & | const_reference
typedef std::size_t | size_type

## Public 成员函数
template<typename InputIterator>
| UnionFind (InputIterator first, InputIterator last)
| 构造并查集
| UnionFind (std::ranges::range auto &&range)
| 构造并查集
bool | connected (const Tp &val_a, const Tp &val_b)
| 两个元素是否在同一个集合
void | merge (const Tp &val_a, const Tp &val_b)
| 将两个元素所在集合合并
std::unordered_map< Tp, std::vector< Tp > > | extract ()
| 导出数据
int | components ()
| 获取连通分量

## Protected 成员函数
Tp | findRep (Tp element)
| 寻找代表元素

## Protected 属性
std::unordered_set< Tp > | _element_set
| 元素集合
std::unordered_map< Tp, Tp > | _parent_map
| 父元素哈希表
std::unordered_map< Tp, std::size_t > | _size_map
| 集合大小
int | _connected_component {}
| 连通分量

## 详细描述

template<typename Tp>
class rm::UnionFind< Tp >

并查集

模板参数

  Tp | 元素类型

## 成员类型定义说明

## ◆ const_reference

template<typename Tp>

typedef const Tp& rm::UnionFind< Tp >::const_reference

## ◆ reference

template<typename Tp>

typedef Tp& rm::UnionFind< Tp >::reference

## ◆ size_type

template<typename Tp>

typedef std::size_t rm::UnionFind< Tp >::size_type

## ◆ value_type

template<typename Tp>

typedef Tp rm::UnionFind< Tp >::value_type

## 构造及析构函数说明

## ◆ UnionFind() [1/2]

template<typename Tp>
template<typename InputIterator>

rm::UnionFind< Tp >::UnionFind | ( | InputIterator | first,
|  | InputIterator | last )
| inline

构造并查集

模板参数

  InputIterator | 老式前向迭代器类型

参数

  [in] | first | 起始迭代器
  [in] | last | 终止迭代器

## ◆ UnionFind() [2/2]

template<typename Tp>

rm::UnionFind< Tp >::UnionFind | ( | std::ranges::range auto && | range | ) |
| inline

构造并查集

参数

  [in] | range | 支持范围 for 的容器

函数调用图:

## 成员函数说明

## ◆ components()

template<typename Tp>

int rm::UnionFind< Tp >::components | ( |  | ) |
| inline

获取连通分量

## ◆ connected()

template<typename Tp>

bool rm::UnionFind< Tp >::connected | ( | const Tp & | val_a,
|  | const Tp & | val_b )
| inline

两个元素是否在同一个集合

参数

  [in] | val_a | 元素 A
  [in] | val_b | 元素 B

返回
  是否在同一个集合

函数调用图:

## ◆ extract()

template<typename Tp>

std::unordered_map< Tp, std::vector< Tp > > rm::UnionFind< Tp >::extract | ( |  | ) |
| inline

导出数据

返回
  Key: 集合代表元素，Value: 集合

函数调用图:

## ◆ findRep()

template<typename Tp>

Tp rm::UnionFind< Tp >::findRep | ( | Tp | element | ) |
| inline protected

寻找代表元素

## ◆ merge()

template<typename Tp>

void rm::UnionFind< Tp >::merge | ( | const Tp & | val_a,
|  | const Tp & | val_b )
| inline

将两个元素所在集合合并

参数

  [in] | val_a | 元素 A
  [in] | val_b | 元素 B

函数调用图:

## 类成员变量说明

## ◆ _connected_component

template<typename Tp>

int rm::UnionFind< Tp >::_connected_component {}
| protected

连通分量

## ◆ _element_set

template<typename Tp>

std::unordered_set<Tp> rm::UnionFind< Tp >::_element_set
| protected

元素集合

## ◆ _parent_map

template<typename Tp>

std::unordered_map<Tp, Tp> rm::UnionFind< Tp >::_parent_map
| protected

父元素哈希表

## ◆ _size_map

template<typename Tp>

std::unordered_map<Tp, std::size_t> rm::UnionFind< Tp >::_size_map
| protected

集合大小