网站免费获取验证码怎么做,全网媒体整合推广平台,企业网站备案去哪里,国外网站建设嫣语赋文章目录 前言代码仓库代码说明main.cppMakefile 结果总结参考资料作者的话 前言
C 代码实例#xff1a;并查集简单创建工具。 代码仓库
yezhening/Programming-examples: 编程实例 (github.com)Programming-examples: 编程实例 (gitee.com) 代码
说明
简单地创建并查集注… 文章目录 前言代码仓库代码说明main.cppMakefile 结果总结参考资料作者的话 前言
C 代码实例并查集简单创建工具。 代码仓库
yezhening/Programming-examples: 编程实例 (github.com)Programming-examples: 编程实例 (gitee.com) 代码
说明
简单地创建并查集注释有详细的步骤解析还可优化的点使用cmake使用右值传递复杂容器减小开销 注半个晚上完成大概测试了下 main.cpp
#include iostream
#include vector
#include algorithm
#include unordered_mapusing std::cout;
using std::endl;
using std::pair;
using std::sort;
using std::unordered_map;
using std::vector;// 并查集类
class DisjointSet
{
public:// 构造并查集// 参数等价关系元素值的大小/范围等价关系集合向量DisjointSet(const int e_q_s, const vectorpairint, int e_r_v) : eq_rel_size(e_q_s), eq_rel_vec(e_r_v){// 1. 初始化元素父节点向量大小是等价关系元素值的大小/范围每个元素的父节点约定为自身this-parent_vec.resize(this-eq_rel_size); // 元素父节点的向量的大小是等价关系元素值的大小/范围for (int i 0; i this-eq_rel_size; i){parent_vec[i] i;}// 2. 初始化元素深度向量大小是等价关系元素值的大小/范围每个元素作为根节点约定为0即第0层// 合并操作依据树的深度优化即优先将深度大的树的根挂接到深度小的树的根this-depth_vec.resize(this-eq_rel_size, 0);// 3. 按照字典序排序等价关系集合向量sort(this-eq_rel_vec.begin(), this-eq_rel_vec.end());// 4. 合并集合for (const auto eq_rel_pair : eq_rel_vec) // 对每一个等价关系集合如{1, 2}{// 4.1 分别查找两关系元素的根节点int first_root this-find_parent(eq_rel_pair.first);int second_root this-find_parent(eq_rel_pair.second);// 4.2 依据根节点情况合并挂接if (first_root second_root) // 相等不操作{continue;}else // first_root ! second_root{if (this-depth_vec[first_root] this-depth_vec[second_root]) // 优先将深度大的树的根挂接到深度小的树的根{this-parent_vec[first_root] second_root;}else if (this-depth_vec[first_root] this-depth_vec[second_root]){this-parent_vec[second_root] first_root;}else // 树的深度相等约定将第二个根挂接到第一个根第一个根的深度加深一层{this-parent_vec[second_root] first_root;this-depth_vec[first_root];}}}// 5. 构建结果unordered_mapint, vectorint root_vec{}; // 哈希表记录 根节点值-该根节点下的元素向量一个向量是一棵新树for (int i 0; i this-eq_rel_size; i) // 遍历元素值{int root this-find_parent(i); // 取根节点root_vec[root].push_back(i);}for (const pairint, vectorint pair_tree : root_vec) // 遍历每棵树加入到结果集{this-disjoint_set.insert(this-disjoint_set.begin(), pair_tree.second);}}// 获取并查集inline vectorvectorint get_disjoint_set() const{return this-disjoint_set;}// 打印并查集inline void print_disjoint_set() const{cout 并查集: endl;for (const vectorint set : this-disjoint_set){for (const int num : set){cout num ;}cout endl;}return;}private:const int eq_rel_size; // 等价关系元素值的大小/范围vectorpairint, int eq_rel_vec; // 等价关系集合向量vectorint parent_vec; // 记录元素父节点的向量vectorint depth_vec; // 记录元素深度的向量约定元素值/树的根是索引根的深度从0、1往上加vectorvectorint disjoint_set; // 并查集并查集类固有的本质内容// 递归查找当前元素值的根节点int find_parent(int x){// 1. 递归逻辑// 如果不是parent[x] ! x则使用当前节点的父节点作为参数调用当前函数递归继续找爷节点find_parent(parent[x])// 把找到的根节点记录在查找路径中每个节点的 元素父节点的向量 中parent_vec[x] // 相当于把该些节点都挂接到根节点上树变得扁平// 即路径压缩优化在并查集中每个元素都有一个父节点通常在查找操作中我们会沿着父节点链一直向上找到根节点// 这个过程就是在寻找元素所在集合的过程。但是在普通的查找操作中路径的长度可能会很长导致后续的查找操作效率较低。// 路径压缩是一种优化技术它的思想是当我们在进行查找操作时不仅找到元素所在集合的根节点// 还顺便将经过的所有节点的父节点都设置为根节点。这样当下次再次查找这些节点时路径就会更短查找效率就会更高。// 如1为根节点23为子节点有1 - 2 - 3的三层树从叶节点3开始找找到1根节点然后依次递归返回把2、3的根节点设置为1// 成为1 - 21 - 3的两层树if (parent_vec[x] ! x){parent_vec[x] find_parent(parent_vec[x]);}// 1. 递归出口// 如果x的父节点是自己说明它是根节点返回// parent_vec[x] x// 把return放在if会有到不了该条件if的警告control reaches end of non-void function [-Wreturn-type]return parent_vec[x];}
};int main()
{const int eq_rel_size 9; // 等价关系元素值的大小/范围const vectorpairint, int eq_rel_vec {{0, 1}, {2, 3}, {4, 5}, {6, 7}, {0, 2}, {4, 6}, {0, 8}}; // 等价关系集合向量内容必须是0~ eq_rel_size - 1并查集类的逻辑定义了DisjointSet ds(eq_rel_size, eq_rel_vec); // 并查集对象ds.print_disjoint_set(); // 打印并查集return 0;
}Makefile
.PHONY : all
all : main.exemain.exe : main.cppg -o $ $^.PHONY : clean
clean :del *.exe结果 总结
C 代码实例并查集简单创建工具。 参考资料
学校《高级算法设计与分析》课程课件的算法思路 作者的话
感谢参考资料的作者/博主作者夜悊版权所有转载请注明出处谢谢~如果文章对你有帮助请点个赞或加个粉丝吧你的支持就是作者的动力~文章在描述时有疑惑的地方请留言定会一一耐心讨论、解答文章在认识上有错误的地方, 敬请批评指正望读者们都能有所收获
