首页
学习
活动
专区
圈层
工具
发布
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    数据结构—并查集《上》

    这是无量测试之道的第175篇原创   今天主要介绍的是并查集这种数据结构。其本质上是解决某一些特定问题的而设计出的数据结构。大家可以了解下这种数据结构,作为自己知识的储备。...通过一个实际的问题引出并查集   假设有 n 个村庄,有些村庄之间有连接的路,有些村庄之间并没有连接的路 设计一个数据结构,能够快速执行 2 个操作: 查询 2 个村庄之间是否有连接的路 连接 2...并查集(Union Find) 并查集也叫作不相交集合(Disjoint Set) 并查集有2个核心操作: 查找(Find):查找元素所在的集合 (这里的集合并不是特指Set这种数据结构,是指广义的数据集合...数组索引代表元素值 索引对应的值代表这个元素的根节点 将{0,1,2,3,4,5,6,7}存储到数组中,如下图:   因此,并查集是可以用数组实现的树形结构(二叉堆、优先级队列也是可以用数组实现的树形结构...) 并查集数据结构的接口定义 /** * 查找v所属的集合(根结点) */ public abstract int find(int v); /** * 合并v1、v2所在的集合 */ public

    78410

    高阶数据结构-并查集

    树形结构展示 并查集的本质就是森林,森林就是很多棵树 森林指针数组展示 指针数组有两个特点: 1、一个位置的值是负数,那它就是树的根,这个负数的绝对值就是这棵树节点的个数 2、一个位置的值是正数,那它就是双亲的下标...回顾全文,并查集作为处理 “动态连通性” 问题的经典数据结构,其核心魅力在于用极简的数组模拟森林,通过高效操作实现集合的管理与查询。...统计集合总数,整个类结构简洁且逻辑闭环。...,真正实现了 “数据结构服务于实际需求”。​...最后想说,学习并查集的意义不仅在于掌握一种工具,更在于理解 “用简单结构解决复杂问题” 的思维:通过抽象元素关系(用数组代森林)、优化操作路径(路径压缩)、平衡结构形态(按大小合并),让看似繁琐的 “集合管理

    35210

    数据结构之并查集

    并查集实际上是一种很不一样的树形结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。...之所以说并查集是一种“不一样”的树形结构,是因为一般的树形结构都是父节点指向子节点的,而并查集则是反过来,子节点指向父节点,并且这棵树会是一棵多叉树。...使用“Quick Union”思路实现并查集时,我们将每一个元素,看做是一个节点。但与普通的树形结构不同的是,并查集的树是子节点指向父节点的,在之前也提到过。如下: ?...我们使用数组来表示树形结构的并查集时,子节点指向父节点的指针实际就是存储父节点的数组索引。而且在初始化后,未进行合并操作时,每个元素都是自己成为一棵树的根节点,代表不同的集合。...也就是说此时会有多棵树,这种情况称之为森林结构,这也是为什么会存在合并两棵树的情况。如下所示: ? 对应的数组表示如下: ?

    1.4K20

    关于linux下DB2创建数据库报错问题

    公司业务需要,把服务搭在中标下,在中标下装了DB2 Express-C v9.7.1,之前用着没有问题,隔了一段时间没用,最近又需要用到它,出了一些菜鸟问题,记录下来以免有人和我犯同样的错误。。。...我出现这个问题的原因是,忘记在终端启动DB2,这个图形化的工具会给大家错觉,让大家以为DB2已经启动,其实这只是个前段的显示工具,不代表数据库已经在运行。...执行 $db2start 然后继续执行上述步骤,发现报错信息 SQL4414N The DB2 Administration Server is not active ......./opt/ibm/db2/V9.7/das/bin/ 把这个路径加入到环境变量中: 先cd 进入用户主目录, vim .bash_profile 在PATH后面加上:/opt/ibm/db2/V9.7/

    3.7K10

    数据结构 - 并查集基础

    引言 并查集是一种数据结构,用于处理一些不交集的合并及查询问题。它常被用来解决连通性问题,如判断两个元素是否属于同一个集合,或者合并两个集合等。并查集的主要操作包括查找和合并。...本文将深入探讨并查集的基本原理,并通过具体的Java代码详细说明并查集的实现步骤。 一、并查集的基本概念 并查集是一种用于管理一组不相交集合的数据结构。...二、并查集的操作 并查集支持以下主要操作: 初始化:创建一个空的并查集。 查找:查找某个元素所属的集合。 合并:将两个集合合并成一个集合。...三、并查集的实现 接下来,我们将通过一个示例来详细了解并查集的实现步骤。 1...." + dsu.isConnected(1, 5)); } } 四、总结 并查集是一种非常实用的数据结构,尤其适用于需要频繁进行集合合并和查询的应用场景。

    48810

    【MySQL】003. MySQL操作库

    创建一个使用utf8字符集的 db2 数据库 create database db2 charset=utf8; create database db2 character set utf8; 创建一个使用...加上匹配条件: select * from person where name='a'; 我们查的时候用utf8mb4_ general_ ci方式把我们要查的和表里的数据进行比较。...5.1 备份 语法: # mysqldump -P3306 -u root -p 密码 -B 数据库名 > 数据库备份存储的文件路径 示例:将test1库备份到文件 sp@hcss-ecs-eaf1:~/linux.practice...5.2 还原 我们将test1删掉后进行还原 source /home/sp/linux.practice/MySQL/test1.sql 将test1.sql全部跑一次 5.3 注意事项 如果备份的不是整个数据库...查看表结构 desc 表名; //查看表的详细信息 查看创建表时候的详细信息: show create table user1 \G; \G的作用是让其格式化输出。 4.

    54900

    DB2 Linux平台安装 Part 4 创建数据库

    从今天开始DB2相关的内容 系统为 Redhat 7.4 数据库为 v10.5fp10 上节我们说了如何建立DB2实例,这节内容为建立数据库 DB2中一个实例下可以有多个数据库,一个数据库只能属于一个实例...建立数据库 接下来我们建立数据库 su - db2inst1 # 如果db2未开启则先开启 db2start db2 CREATE DATABASE testdb ON /db2data USING...然后我们连接数据库 db2 activate db testdb db2 connect to testdb 3....数据库目录结构 当执行完上面的语句后,我们来看下DB2到底新建了什么 /home/db2inst1/sqllib下面 在家目录的sqllib下面新建了一个sqldbdir目录 ?.../db2data目录里面 在创建数据库的时候我们指定了容器(数据文件)的目录 DB2会在该目录下建立如下目录,为本地数据库编录目录 /db2data/db2inst1/NODE0000 其中db2inst1

    3.1K21

    Python笔记:并查集(DSU)结构简介

    并查集是什么 并查集(Disjoint Set Union)是一种常用的处理不相交集合间的合并与查找功能的树形结构,配合与之对应的联合-搜索算法(Union Find Algorithm),可以将不相交集合间的合并与查找功能的时间复杂度大幅缩减至...= y: self.root[y] = x return 上述代码即为最为一般性的并查集结构。 2....调整树形结构 为了更好地优化算法的效率,我们可以控制树形结构,使其尽可能地扁平化,避免出现链型结构导致深度过深,我们经常会通过记录树的深度的方式优化树形结构,从而优化算法效率。...Leetcode例题分析 下面,我们来通过一些leetcode中的例题来考察并查集结构的实际用法。 1. Leetcode 547....Friend Circles 这一题是最为典型的并查集使用场景,我们直接套用并查集结构就能解答这道题。

    4.6K31
    领券